今天学习了一下碰撞指针的用法,就写了这道经典的题目
题目如下:
给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。
LeetCode.167
一开始我就想到了碰撞指针,但是不知道为什么我的时间复杂度非常高,
先讲一下我的思路:
定义两个指针,L指向nums[ 0 ] ,R 指向 num[ len-1 ],然后在保证L 小于
R的情况下,如果比 target 小就L++,大就R–,否则返回
这里有两个难点:
1.由于有重复的元素,如何保证R已经指向某元素的第一个位置?
我们可以增加判断条件
if(nums[R] + nums[L] == target && nums[R] != num[R-1])
2.这样又会出现一个问题,那就是如果两个目标元素相邻且相等怎么办?
我又进行了特判,并修改上面的代码
if(numbers[l] + numbers[r] == target && numbers[r] != numbers[r-1] && r - l > 1)
{
return {l+1,r+1};
}
else if(numbers[l] + numbers[r] == target && r - l == 1){
return {l+1,r+1};
}
感觉代码十分的臃肿。于是我看了一下官方的答案:
class Solution {
public:
vector twoSum(vector& numbers, int target) {
int low = 0, high = numbers.size() - 1;
while (low < high) {
int sum = numbers[low] + numbers[high];
if (sum == target) {
return {low + 1, high + 1};
} else if (sum < target) {
++low;
} else {
--high;
}
}
return {-1, -1};
}
};
我发现我把题目想复杂了,我的理解是:
比如数组为:
1 2 32 40 40 40 42 43
然后 target = 41,然后我们的返回值为[1,4];
但是题目的意思是不会出现这种情况,只会有两个固定的位置的和为target。



