你管这破玩意叫“对撞指针”？
本文由一道 leetcode 简单题，引出在刷题和笔试经常用到的双指针中的“对撞指针”解题技巧，供大家参考，希望能对大家有所帮助。
两数之和 II - 输入有序数组
给定一个已按照升序排列的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标从 1 开始计数，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
解题思路
要从数组中找出两个数满足之和等于目标数，最直观的解法就是通过暴力枚举。两层遍历数组所有的下标 i j 对，再判断其对应的数组元素和是否等于目标数，找到则直接返回，否则就无解。时间复杂度为 (O^2)。
Show me the Code
// c 语言 暴力枚举
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
*returnSize = 0;
/* 输入校验 */
if (numbers == NULL || numbersSize <= 0) {
return NULL;
}
/* 申请一块内存空间，判断是否分配成功 */
int *res = (int *)malloc(2 * sizeof(int));
if (res == NULL) {
return NULL;
}
memset(res, 0, 2 * sizeof(int));
for (int i = 0; i < numbersSize; ++i) {
for (int j = i + 1; j < numbersSize; ++j) {
/* 双层遍历，查找数组中是否存在两个元素和等于目标值 */
if (numbers[i] + numbers[j] == target) {
res[0] = i + 1;
res[1] = j + 1;
*returnSize = 2;
return res;
}
}
}
return NULL;
}
运行结果
进一步分析
从上面的运行结果，可以看出暴力枚举速度太慢了，是不是有更快的方法呢？答案是有的，由于题目中已经明确告知了所给的数组是“升序排列”的，即数组是有序的，所以可以通过二分查找去做。此时时间复杂度降为 O(n * lgn)。
Show me the Code
// c语言 二分查找
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
*returnSize = 0;
if (numbers == NULL || numbersSize <= 0) {
return NULL;
}
int *res = (int *)malloc(2 * sizeof(int));
if (res == NULL) {
return NULL;
}
memset(res, 0, 2 * sizeof(int));
/* 遍历整个数组，固定一个数 numbers[i]，通过二分查找 另外一个数 target - numbers[i] */
for (int i = 0; i < numbersSize; ++i) {
int l = i + 1, r = numbersSize - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
int val = target - numbers[i];
if (numbers[mid] < val) {
l = mid + 1;
} else if (numbers[mid] > val) {
r = mid - 1;
} else {
/* 返回的是原数组下标加 1 */
res[0] = i + 1;
res[1] = mid + 1;
*returnSize = 2;
return res;
}
}
}
return NULL;
}
运行结果
更进一步分析
从上面的通过二分查找方法得到的运行结果可以看出，相比于暴力枚举，二分查找速度快了不少，但通过二分查找时间复杂度为
O(n * lgn)，有没有时间复杂度更低 (O(n)）的方法呢？答案是有的，这就是今天要讲的“对撞指针”。
对撞指针
对撞指针：在有序数组中，定义指向最左侧的索引为左指针(left)，最右侧的为右指针（right），然后从数组两头向中间进行遍历。如下图示：
Show me the Code
// c语言 对撞指针
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
*returnSize = 0;
if (numbers == NULL || numbersSize <= 0) {
return NULL;
}
int* res = (int *)malloc(2 * sizeof(int));
if (res == NULL) {
return NULL;
}
memset(res, 0, 2 * sizeof(int));
int left = 0, right = numbersSize - 1;
while (left <= right) {
int value = numbers[left] + numbers[right];
if (value == target) {
break;
} else if (value < target) {
left++;
} else {
right--;
}
}
res[0] = left + 1;
res[1] = right + 1;
*returnSize = 2;
return res;
}腾讯云开发者
