双指针算法解决有序数组两数之和问题
1. 题目解析与核心思路
167题是经典"两数之和"问题的变种，题目给定一个已按非递减顺序排列的整数数组numbers和一个目标值target。要求找出两个数使它们相加之和等于目标数，并返回这两个数的下标（下标从1开始）。
与原始两数之和问题相比，这个变种的关键差异在于：
- 输入数组已经有序（非递减顺序）
- 要求返回的下标从1开始计数
- 保证有且仅有一个解
1.1 暴力解法分析
最直观的解法是双重循环暴力枚举：
for i in range(len(numbers)): for j in range(i+1, len(numbers)): if numbers[i] + numbers[j] == target: return [i+1, j+1]时间复杂度O(n²)，空间复杂度O(1)。虽然能通过但显然没有利用数组有序的特性。
1.2 哈希表解法优化
借鉴原始两数之和的哈希表解法：
hashmap = {} for i, num in enumerate(numbers): complement = target - num if complement in hashmap: return [hashmap[complement]+1, i+1] hashmap[num] = i时间复杂度O(n)，空间复杂度O(n)。比暴力解法优化但仍未充分利用数组有序的特性。
2. 双指针算法详解
针对有序数组的特性，双指针算法是最优解：
2.1 算法原理
- 初始化左右指针：left=0, right=len(numbers)-1
- 计算当前和：current_sum = numbers[left] + numbers[right]
- 比较current_sum与target：
- 等于target：返回[left+1, right+1]
- 小于target：left右移（增大和）
- 大于target：right左移（减小和）
- 重复直到找到解
2.2 Python实现
def twoSum(numbers, target): left, right = 0, len(numbers) - 1 while left < right: current_sum = numbers[left] + numbers[right] if current_sum == target: return [left + 1, right + 1] elif current_sum < target: left += 1 else: right -= 1 return [-1, -1] # 题目保证有解，这行不会执行2.3 复杂度分析
- 时间复杂度：O(n)，最坏情况下遍历整个数组一次
- 空间复杂度：O(1)，只使用了常数个额外空间
3. 算法正确性证明
双指针算法的正确性基于以下数学原理：
单调性保证：数组有序意味着：
- 固定left，numbers[right]是能与numbers[left]配对的最大值
- 固定right，numbers[left]是能与numbers[right]配对的最小值
搜索空间缩减：
- 当numbers[left]+numbers[right]<target时，对于left'<=left，numbers[left']+numbers[right]必定也小于target
- 当numbers[left]+numbers[right]>target时，对于right'>=right，numbers[left]+numbers[right']必定也大于target
这种性质确保了我们可以安全地移动指针而不会错过解。
4. 边界条件与测试用例
4.1 典型测试用例
# 常规情况 assert twoSum([2,7,11,15], 9) == [1,2] # 解在数组两端 assert twoSum([-1,0,3,5,9,12], 11) == [3,5] # 包含重复元素 assert twoSum([1,2,2,3], 4) == [2,3] # 最小规模数组 assert twoSum([1,2], 3) == [1,2]4.2 特殊注意事项
- 下标从1开始：返回时需要+1
- 不要使用相同的元素两次：while条件是left<right而非left<=right
- 题目保证有解：无需处理无解情况
5. 算法优化与变种
5.1 提前终止优化
当numbers[left] > target/2时，可以提前终止：
while left < right: if numbers[left] > target / 2: break # 原逻辑...5.2 二分查找结合
可以在移动指针时结合二分查找快速定位：
elif current_sum < target: # 在[left+1, right]区间二分查找target-numbers[right] left = bisect.bisect_left(numbers, target-numbers[right], left+1, right+1) - 15.3 多解情况处理
如果题目允许/要求返回所有解：
result = [] while left < right: current_sum = numbers[left] + numbers[right] if current_sum == target: result.append([left+1, right+1]) # 处理重复元素 while left < right and numbers[left] == numbers[left+1]: left += 1 while left < right and numbers[right] == numbers[right-1]: right -= 1 left += 1 right -= 1 elif current_sum < target: left += 1 else: right -= 1 return result6. 同类题目延伸
掌握双指针技巧后，可以解决许多类似问题：
- 三数之和（LeetCode 15）
- 最接近的三数之和（LeetCode 16）
- 盛最多水的容器（LeetCode 11）
- 验证回文串（LeetCode 125）
- 合并两个有序数组（LeetCode 88）
这类问题的共同特点是都利用了有序数组的特性，通过指针移动来高效搜索解空间。
7. 实际工程应用
双指针算法在实际工程中有广泛应用场景：
- 数据库查询优化：合并两个有序结果集
- 版本控制系统：比较两个版本的文件差异
- 大数据处理：合并多个有序数据流
- 游戏开发：碰撞检测中的空间分区优化
理解这类算法不仅能帮助通过面试，更能提升解决实际工程问题的能力。我在处理日志合并任务时就曾应用类似的技巧，将处理时间从O(n²)优化到O(n)。