Two-Sum

Veröffentlicht am

Question

给定一个整型数组，返回两个数的索引，这两个数之和等于目标值。你可以认为每一组输入只有一个解，并且不允许使用一个数两次.
例如：
给定nums=[2,7,11,15],target=9,由于nums[0]+nums[1]=target,所以返回[0,1].

Solution

Approach #1(Brute Force)

遍历每一个数以寻找另一个数等于$target-x$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> twoSum(vector<int>& nums, int target){
    vector<int> result;
    int i = 0;
    int j = 0;
    int s = nums.size();
    int s_ = s-1;
    for(; i<s_; i++){
        for(j=i+1; j<s; j++){
            if((target-nums[i])==nums[j]){
                result.push_back(i);
                result.push_back(j);
                break;
            }
        }
    }
    return result;
}

  • Time complexity: $O(n^2)$. 对于每一个数，寻找另一个数所花时间是$O(n)$.
  • Space complexity: $O(1)$.

Apporoach #2(One-pass Hash Table)

同样，我们遍历每一个数来寻找是不是存在第二个数等于$target-x$，但是借助于HashTable结构可以将寻找过程的时间复杂度从$O(n)$降到$(O(1)$. 为了使用HashTable结构加快搜索，我们需要在寻找的同时维护一个从数到索引的映射表.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        unordered_map<int, int> table;
        int j = 0;
        int s = nums.size();
        for(; j<s; j++){
            if(table.find(target-nums[j]) != table.end()){
                result.push_back(table.at(target-nums[j]));
                result.push_back(j);
                break;
            }
            table[nums[j]] = j;
        }
        return result;
    }

  • Time complexity: $O(n)$. 我们仅仅遍历数组一次，每一次查询时间是$O(1)$.
  • Space complexity: $O(n)$. 我们需要额外的空间来维护一个映射表，这个表最多会存储$n$个元素.