1. Two Sum (Easy)

准备开始找工作,代码必不可少。想起毕业那会,刷了一阵子LeetCode,还花了不少大洋了,可是总是草草而终,没有认真理解每道题目的要义,为了刷而刷,实在没有任何长进啊~现在是时候认真总结过一遍了。

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

我的思路:采用两个循环暴力寻找合适的组合方法,算法的时间复杂度为O(n^2)。代码如下,运行时间182ms,排在27.89%的位置,太慢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
for(int i=0; i<nums.size(); i++){
for(int j=i+1; j<nums.size(); j++){
if(nums[i] + nums[j] == target){
res.push_back(i);
res.push_back(j);
return res;
}
}
}
}
};

网上看了一下其他人的解答。优化方法有两种,第一种是用哈希表,时间复杂度为O(n), 同时空间复杂度也是O(n);第二种方法是先对数组进行排序,然后使用夹逼的方法找出满足条件的组合。该算法的时间复杂度为O(nlogn+n)=O(nlogn),空间复杂度取决于排序算法。

哈希表解法1如下(时间9ms,排在92.29%):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
vector<int> res;
for(int i=0; i<nums.size();i++){
m[nums[i]] = i;
}
for(int i=0; i<nums.size();i++){
int t = target - nums[i];
if (m.count(t) && m[t] != i){
res.push_back(i);
res.push_back(m[t]);
break;
}
}
return res;

}
};

哈希表解法2如下(时间10ms,排名70.97%)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
vector<int> res;
for(int i=0; i<nums.size(); i++){
int t = target - nums[i];
if(m.count(t) && m[t] != i){
res.push_back(i);
res.push_back(m[t]);
break;
}
m[nums[i]] = i;
}
return res;
}
};

先排序,再夹逼解法如下(7ms, 排名98.73%,效率非常快)

将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
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>& nums, int target) {
vector<int> res(2, -1);
vector<elem> arr;
for(int i=0; i<nums.size();i++){ arr.push_back(elem(nums[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] = arr[left].index;
res[1] = arr[right].index;
break;
}
else if(arr[left].val + arr[right].val<target)
left++;
else
right--;
}
return res;
}
};