[LeetCode]兩兩加總(Two Sum)

題目描述

給定一個nums整數陣列和一個整數target，回傳加總會等於target的兩個不同的元素的索引值。

您可以假設每筆測資只會有剛好一個解。

回傳的索引值可以是任意的順序。

原題網址

https://leetcode.com/problems/two-sum/

輸入格式

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹

輸出格式

用整數陣列回傳索引值。

範例輸入1

nums = [2, 7, 11, 15]
target = 9

範例輸出1

[0, 1]

範例輸入2

nums = [3, 2, 4]
target = 6

範例輸出2

[1, 2]

範例輸入3

nums = [3, 3]
target = 6

範例輸出3

[0, 1]

題解

這題最直覺的方式就是先從陣列第一個元素開始走訪，每走訪一個元素，就去與其之後的元素逐一做加法，並判斷加法運算之後的值是否就是目標值，是的話就直接回傳答案。

然而這種做法的時間複雜度為#{{O(n^2)}}#，如果要到達最快的話，必須使用截然不同的方式。

我們可以一開始的時候，把第一個元素值和索引值用一個Map結構來記錄下來，之後從陣列第二個元素開始走訪。在每次迭代的時候，先計算目標值減目前走訪到的元素值的差，利用這個差值作為Map結構的鍵值來進行搜尋，如果有搜尋到就表示我們先前就已經有讀取到與這個差值相等的元素值了，換句話說，在Map結構中被成功搜尋到的元素值再加上目前走訪到的元素值就會等於目標值，而我們也知道Map結構中被成功搜尋到的元素值的索引值，因此就可以得到題目要的答案啦！如果該次迭代所計算的差值不是當時Map結構的鍵值的話，要把該次迭代的元素值和索引值儲存進Map結構中，之後才能查詢。如此一來，便實現出時間複雜度為#{{O(n)}}#的演算法了，雖然這樣會需要額外的空間來儲存先前讀取過的元素值和索引值，但這個記憶體花費是很划算的。

參考答案

use std::collections::BTreeMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut map: BTreeMap<i32, i32> = BTreeMap::new();

        map.insert(nums[0], 0);

        for (j, &b) in nums[1..].iter().enumerate() {
            let j = j as i32 + 1;

            let d = target - b;

            if let Some(&i) = map.get(&d) {
                return vec![i as i32, j];
            }

            map.insert(b, j);
        }

        vec![]
    }
}

const twoSum = (nums: number[], target: number): number[] => {
    const map: {[_: number]: number} = {};

    map[nums[0]] = 0;

    for (let i = 1;i < nums.length;i++) {
        const num = nums[i];

        const d = target - num;

        if (Object.prototype.hasOwnProperty.call(map, d)) {
            return [i, map[d]];
        }

        map[num] = i;
    }

    return [];
};