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 算法原理

1. 初始化左右指针：left=0, right=len(numbers)-1
2. 计算当前和：current_sum = numbers[left] + numbers[right]
3. 比较current_sum与target：
   • 等于target：返回[left+1, right+1]
   • 小于target：left右移（增大和）
   • 大于target：right左移（减小和）
4. 重复直到找到解

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. 算法正确性证明

双指针算法的正确性基于以下数学原理：

1. 单调性保证：数组有序意味着：

   • 固定left，numbers[right]是能与numbers[left]配对的最大值
   • 固定right，numbers[left]是能与numbers[right]配对的最小值

2. 搜索空间缩减：

   • 当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开始：返回时需要+1
2. 不要使用相同的元素两次：while条件是left<right而非left<=right
3. 题目保证有解：无需处理无解情况

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) - 1

5.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 result

6. 同类题目延伸

掌握双指针技巧后，可以解决许多类似问题：

1. 三数之和（LeetCode 15）
2. 最接近的三数之和（LeetCode 16）
3. 盛最多水的容器（LeetCode 11）
4. 验证回文串（LeetCode 125）
5. 合并两个有序数组（LeetCode 88）

这类问题的共同特点是都利用了有序数组的特性，通过指针移动来高效搜索解空间。

7. 实际工程应用

双指针算法在实际工程中有广泛应用场景：

1. 数据库查询优化：合并两个有序结果集
2. 版本控制系统：比较两个版本的文件差异
3. 大数据处理：合并多个有序数据流
4. 游戏开发：碰撞检测中的空间分区优化

理解这类算法不仅能帮助通过面试，更能提升解决实际工程问题的能力。我在处理日志合并任务时就曾应用类似的技巧，将处理时间从O(n²)优化到O(n)。