[LeetCode] Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

思路1：hash table

对于数组中每个数来A[i]来说，需要在数组的其他元素中寻找target - A[i]。所以问题转化为数组查找元素问题，当给定一个值时，需要能快速判断是否存在于数组中，如果存在，index是多少。

可以将所有元素插入一个hash table <key = A[i], val = i>，然后重新遍历每个元素，计算target - A[i]，然后在hash table中查找。这里仍需解决2个问题：

(1) 重复元素的问题：比如{2 2 3}, target = 4。解决方法为hash table的val变为一个vector<int>来记录所有j：A[j] = A[i]。

(2) index 1 < index 2：假设A[i] + A[j] = target并且i<j。那么在遍历查找时从左向右，一定在扫描i的时候就找到个solution。返回按照这个顺序即可。

时间和额外空间复杂度均为O(n)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

class Solution { public: vector<int> twoSum(vector<int> &numbers, int target) { vector<int> res; int first = -1, second = -1; unordered_map<int, vector<int> > ht; for(int i=0; i<numbers.size(); i++) ht[numbers[i]].push_back(i); for(int i=0; i<numbers.size(); i++) { int val = target - numbers[i]; if(ht.count(val)) { if(numbers[i]!=val) { first = i+1; second = ht[val][0]+1; break; } else if(ht[val].size()>1) { first = ht[val][0]+1; second = ht[val][1]+1; break; } } } res.push_back(first); res.push_back(second); return res; } };

思路2：two pointers

将array排序，双指针left/right分别指向头尾。然后两个指针分别向中间移动寻找目标。
(1) A[left] + A[right] = target：直接返回(left+1, right+1)。
(2) A[left] + A[right] > target：说明A[right]不可能是解，right--
(3) A[left] + A[right] < target：说明A[left]不可能是解，left++

中止条件：left >= right

但排序会打乱原来数组index的顺序。我们可以建立一个class/struct/pair来存储val/index，并overload operator < 来以val值排序。这样我们可以track排序后每个数的原有index。

重复元素这里无须特殊处理。index 1和index 2分别取找到的两个index的min/max即可。时间复杂度由于排序的关系为O(n log n)，额外空间复杂度O(n)。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class Solution { class elem { public: int val; int index; elem(int v, int i):val(v),index(i) {} bool operator<(const elem &e) const { return val<e.val; } }; public: vector<int> twoSum(vector<int> &numbers, int target) { vector<int> res(2,-1); vector<elem> arr; for(int i=0; i<numbers.size(); i++) arr.push_back(elem(numbers[i],i)); sort(arr.begin(),arr.end()); int left = 0, right = arr.size()-1; while(left<right) { if(arr[left].val+arr[right].val==target) { res[0] = min(arr[left].index,arr[right].index)+1; res[1] = max(arr[left].index,arr[right].index)+1; break; } else if(arr[left].val+arr[right].val<target) left++; else right--; } return res; } };