## Saturday, November 15, 2014

### [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) 重复元素的问题：比如{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。返回按照这个顺序即可。

 ``` 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 twoSum(vector &numbers, int target) { vector res; int first = -1, second = -1; unordered_map > ht; for(int i=0; i1) { first = ht[val][0]+1; second = ht[val][1]+1; break; } } } res.push_back(first); res.push_back(second); return res; } }; ```

(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++

 ``` 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 twoSum(vector &numbers, int target) { vector res(2,-1); vector arr; for(int i=0; i

#### 1 comment:

1. res[0] = min(arr[left].index,arr[right].index)+1;
res[1] = max(arr[left].index,arr[right].index)+1;

这两句末尾不用加一吧？