双指针算法解决有序数组两数之和问题

1. 题目解析与核心思路167题是经典两数之和问题的变种题目给定一个已按非递减顺序排列的整数数组numbers和一个目标值target。要求找出两个数使它们相加之和等于目标数并返回这两个数的下标下标从1开始。与原始两数之和问题相比这个变种的关键差异在于输入数组已经有序非递减顺序要求返回的下标从1开始计数保证有且仅有一个解1.1 暴力解法分析最直观的解法是双重循环暴力枚举for i in range(len(numbers)): for j in range(i1, len(numbers)): if numbers[i] numbers[j] target: return [i1, j1]时间复杂度O(n²)空间复杂度O(1)。虽然能通过但显然没有利用数组有序的特性。1.2 哈希表解法优化借鉴原始两数之和的哈希表解法hashmap {} for i, num in enumerate(numbers): complement target - num if complement in hashmap: return [hashmap[complement]1, i1] hashmap[num] i时间复杂度O(n)空间复杂度O(n)。比暴力解法优化但仍未充分利用数组有序的特性。2. 双指针算法详解针对有序数组的特性双指针算法是最优解2.1 算法原理初始化左右指针left0, rightlen(numbers)-1计算当前和current_sum numbers[left] numbers[right]比较current_sum与target等于target返回[left1, right1]小于targetleft右移增大和大于targetright左移减小和重复直到找到解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. 算法正确性证明双指针算法的正确性基于以下数学原理单调性保证数组有序意味着固定leftnumbers[right]是能与numbers[left]配对的最大值固定rightnumbers[left]是能与numbers[right]配对的最小值搜索空间缩减当numbers[left]numbers[right]target时对于leftleftnumbers[left]numbers[right]必定也小于target当numbers[left]numbers[right]target时对于rightrightnumbers[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条件是leftright而非leftright题目保证有解无需处理无解情况5. 算法优化与变种5.1 提前终止优化当numbers[left] target/2时可以提前终止while left right: if numbers[left] target / 2: break # 原逻辑...5.2 二分查找结合可以在移动指针时结合二分查找快速定位elif current_sum target: # 在[left1, right]区间二分查找target-numbers[right] left bisect.bisect_left(numbers, target-numbers[right], left1, right1) - 15.3 多解情况处理如果题目允许/要求返回所有解result [] while left right: current_sum numbers[left] numbers[right] if current_sum target: result.append([left1, right1]) # 处理重复元素 while left right and numbers[left] numbers[left1]: 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)。