- 正确答案：使用双指针法，在已排序的数组中，初始化左指针指向首元素（索引0），右指针指向末元素（索引n-1）；计算两指针指向元素之和sum = numbers[left] + numbers[right]；若sum等于target，返回[left+1, right+1]（题目要求1-based索引）；若sum < target，说明需要更大值，左指针右移；若sum > target，说明需要更小值，右指针左移；重复直到找到解或left >= right。 - 解答思路：本题区别于普通两数之和（LeetCode 1），关键约束是输入数组numbers已升序排列，且有唯一解。因此无需哈希表O(n)空间，可利用单调性设计O(1)空间、O(n)时间的双指针扫描策略。其本质是“收缩搜索区间”：每次比较sum与target后，至少能安全排除一行或一列在二维隐式搜索空间中的候选对（类比矩阵中从右上角开始搜索）。由于数组有序，移动任一指针都具有明确方向性——左移减小sum，右移增大sum，故不会遗漏解。 - 深度知识讲解： 1. **双指针范式分类**：本题属于“相向双指针（Converging Two Pointers）”，与“快慢指针（Floyd判圈）”“同向双指针（滑动窗口）”并列为三大基础范式。相向双指针的核心前提是序列有序（或可排序），通过维护左右边界实现线性扫描，避免O(n²)暴力枚举。 2. **数学正确性证明（不变式）**：设真实解为(i, j)，i < j。初始时left=0, right=n-1，必有left ≤ i 且 right ≥ j。假设某步left' < i 且 right' > j，此时若sum = numbers[left'] + numbers[right'] < target，则因numbers[i] ≥ numbers[left'] 且 numbers[j] ≤ numbers[right']，有numbers[i] + numbers[j] ≥ numbers[left'] + numbers[j] > numbers[left'] + numbers[right']（？不成立），需换角度：实际证明采用反证法——若当前left' < i 且 right' > j，且sum < target，则因numbers单调增，对任意k ∈ [left'+1, right']，有numbers[left']+numbers[k] ≥ numbers[left']+numbers[left'+1] > numbers[left']+numbers[left']（无直接帮助）。更严谨的不变式是：“在每一步迭代前，真实解(i,j)一定落在闭区间[left, right]内”。初始成立；若sum < target，则对所有k ≤ left，numbers[k] + numbers[right] ≤ numbers[left] + numbers[right] < target ⇒ (k,right)不可能是解 ⇒ 可安全left++；同理sum > target ⇒ numbers[left] + numbers[k] ≥ numbers[left] + numbers[right] > target ⇒ (left,k)不可能是解 ⇒ 可安全right--。因此解始终保留在[left, right]内，算法不会漏解。 3. **底层数据结构无关性**：该算法不依赖具体数据结构实现，仅需支持O(1)随机访问的线性结构（如数组、vector）。若输入为链表，则无法高效访问尾部，需先转数组或改用哈希法——凸显了“访问模式”对算法选择的决定性影响。 4. **边界与鲁棒性**：题目保证有唯一解，故无需处理未找到情况；但工业级代码应加防御性检查（如left < right循环条件，避免越界）；若扩展为“返回所有解”，则需跳过重复元素（while left < right && numbers[left] == numbers[left+1]: left++），体现去重逻辑。 5. **对比哈希法**：哈希法时间O(n)、空间O(n)，适用于无序数组；双指针时间O(n)、空间O(1)，但强依赖有序性。二者trade-off本质是“空间换随机访问能力” vs “有序性换空间节省”。 - 伪代码： ``` function twoSum(numbers, target): left = 0 right = length(numbers) - 1 while left < right: sum = numbers[left] + numbers[right] if sum == target: return [left + 1, right + 1] // 1-based indexing else if sum < target: left = left + 1 else: right = right - 1 return [] // 题目保证有解，此行为防御性补充 ``` - 补充代码（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 # 需要更大的左操作数，故右移left else: right -= 1 # 需要更小的右操作数，故左移right return [] # 理论上不会执行到此处 - 扩展思考： - 若数组无序，能否用双指针？答：必须先排序，但排序会破坏原下标，需用（值, 原索引）元组排序，时间O(n log n)，空间O(n)，此时不如直接哈希O(n)。 - 若求三数之和（LeetCode 15），可固定一数，对剩余部分用双指针，复杂度O(n²)。 - 若扩展为“两数之和小于target的对数”，则当numbers[left] + numbers[right] < target时，所有(left, right'), right' ∈ [left+1, right]均满足，可批量计数：count += right - left，然后left++ —— 体现双指针在计数类问题中的高效性。

阿里通义实验室二面凉经

全站热榜

创作者周榜