思路
双指针的经典题目,建议看这篇题解。多嘴说一句,这道题哈希虽然也可以AC,但是面试的时候千万不要用哈希表…印象分肯定会大打折扣的
双指针代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int len = nums.size();
if(!len)
return {};
int i = 0, j = len - 1;
while(i < j){
if(nums[i] + nums[j] < target)
i ++ ;
else if(nums[i] + nums[j] > target)
j -- ;
else
return {nums[i], nums[j]};
}
return {};
}
};
哈希(尽量别用)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int len = nums.size();
if(!len)
return {};
unordered_set<int> dict;
for(int i = 0; i < len; i ++ ){
if(dict.count(target - nums[i]))
return {nums[i], target - nums[i]};
else
dict.insert(nums[i]);
}
return {};
}
};