167 两数之和 II - 输入有序数组
如果仿效1 两数之和,也能过。但是题目要求空间复杂度为\(O(1)\)这种做法显然不满足
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
unordered_map<int,int> hashMap;
for(int i = 0; i < numbers.size(); i++){
int sum = target - numbers[i];
if(hashMap.count(sum)){
return {hashMap[sum], i + 1};
}
hashMap[numbers[i]] = i + 1;
}
return {};
}
};
既然都给了排序,那么我们不需要使用哈希表了,直接使用双指针就可以了
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size() - 1;
// 不能使用两次相同元素, left == right不能成立
while(left < right){
if(numbers[left] + numbers[right] == target){
return {left + 1, right + 1};
}else if(numbers[left] + numbers[right] < target){
left++;
}else if(numbers[left] + numbers[right] > target){
right--;
}
}
return {};
}
};