Description
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:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
思路
首先我们想到的是暴力法，两个 for 循环求解，时间复杂度为O(n^2)
//Runtime: 106 ms
//First thought: BF
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int i,j;
vector<int> ret {, };
for (i = ; i< nums.size(); ++i) {
ret[] = i;
for(j = i+; j < nums.size(); ++j){
if (nums[i] + nums[j] == target)
{
ret[] = j;
return ret;
}
}
}
}
};
但是，我发现时间消耗太多了，所以借鉴当时“换硬币”、“爬楼梯”问题的优化方法，由于num[i]、num[j]、target都是定值，所以在条件判断里不需要每次都进行加运算
//Runtime: 79 ms
//Because nums[i], nums[j], target are fixed values, we do not need to do additions every time
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int i,j;
vector<int> ret {, };
for (i = ; i< nums.size(); ++i) {
ret[] = i;
int tar = target - nums[i];
for(j = i+; j < nums.size(); ++j){
if (nums[j] == tar)
{
ret[] = j;
return ret;
}
}
}
}
};
AC后，看了 Discuss 里头的方法以及娄神的博客，我采用了更复杂的数据结构 散列表（HashTable）以降低时间复杂度，我的想法是这样： 如果想只扫描一遍数组就得出结果，那么肯定就要有一部字典，边扫描边存储值，在这里存储的不是数组当前的值，而是“目标值 - 当前值”，我们称之为对象值。
也就是说，字典里存储的是每个数据所希望的”另一半“的大小。所以，字典的 Key 是对象值，字典的 Value 是数组索引。然后我们再往后扫描，如果扫描到的值的另一半出现在了字典里，那么说明当前值是”上一半“所需要的”下一半“，此时将它们的索引存储在 ret[0]、ret[1]中并返回；如果没有字典里没有出现它的另一半，那么把对象值和当前索引继续存储字典中。
该算法的时间复杂度为 O(n)
//Runtime: 6 ms #include<unordered_map>
using std::unordered_map; class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> um;
vector<int> res();
int i;
int n = nums.size();
for (i = ; i < n; ++i) {
if (um.find(target - nums[i]) != um.end()) {
res[] = um[target - nums[i]];
res[] = i;
return res;
}
else {
um[nums[i]] = i;
}
}
um.clear();
}
};
补充一种双指针遍历有序数组的方法
TwoNumberSum (S, x)
mergeSort (S, , n)
i =
j = n
while i < j
if A[i] + A[j] == x
return true
if A[i] + A[j] < x
i = i +
if A[i] + A[j] > x
j = j -
return false
可以看得出来，查找的时间仅需 Θ(n)，所以时间总代价受排序时间代价的影响，为Θ(n lgn)
扫描的原理很简单，先设 mi,j : A[i] + A[j] < S，Mi,j : A[i] + A[j] > S 。由于序列已排序，则 mi,j ⇒∀k < j 都有 mi,k 成立，并且 Mi,j ⇒ ∀k > i 都有 Mk,j 成立