解法一:O(N)
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int, int> numsHash;
vector<int> res; for (int i = ; i < nums.size(); ++i) {
int num_last = target - nums[i];
if (numsHash.find(num_last) != numsHash.end()) {
res.push_back(numsHash[num_last] + );
res.push_back(i + );
break;
} else {
numsHash[nums[i]] = i;
}
}
return res;
}
解法二:O(NlogN)
vector<int> twoSum(vector<int>& nums, int target)
{
vector<int> res;
int lpos = , rpos = nums.size() - ;
sort(nums.begin(), nums.end());
while (lpos < rpos) {
int num = nums[lpos] + nums[rpos];
if (num == target) {
res.push_back(lpos + );
res.push_back(rpos + );
} else if (num > target) {
rpos--;
} else {
lpos++;
}
}
return res;
}
解法二也是不错的思路,空间复杂度O(1),但这个解法会超时。