排序算法之：利用“双指针法”对“已排序数组中的两数之和”问题进行高效求解
字数 2501 2025-12-23 02:49:25

排序算法之：利用“双指针法”对“已排序数组中的两数之和”问题进行高效求解

题目描述

给定一个已经按升序排列的整数数组 nums，以及一个目标值 target。请你找出数组中两个不同的元素，使得它们的和等于 target，并返回这两个元素的索引（通常假设索引从 1 开始）。题目保证有且只有一个有效答案。

例如：

  • 输入：nums = [2, 7, 11, 15], target = 9
  • 输出：[1, 2] (因为 nums[1] + nums[2] = 2 + 7 = 9)

本题的核心在于利用数组已排序的特性，设计出比暴力枚举更高效的算法。

解题过程

第一步：暴力解法分析（作为起点和对比）

最直观的想法是使用两层循环，枚举所有可能的数对 (i, j)（其中 i < j），检查它们的和是否为 target。

  • 时间复杂度：O(n²)，其中 n 是数组长度。
  • 空间复杂度：O(1)。
    这种方法没有利用数组已排序的性质，效率低下，但思路简单，有助于我们理解问题。

第二步：引入关键观察——已排序数组的性质

由于数组是升序排列的，数组中的元素具有以下性质：

  1. 如果固定一个较小的数 nums[i]，那么要想和达到 target，另一个数必须是一个较大的数 nums[j]。
  2. 当我们从数组的两端同时向中间遍历时，可以通过比较当前和与 target 的大小关系，智能地移动指针，从而避免不必要的枚举。

第三步：设计双指针算法

我们定义两个指针：

  • 左指针 left：初始指向数组的第一个元素（最小元素），索引为 0。
  • 右指针 right：初始指向数组的最后一个元素（最大元素），索引为 n - 1。

算法步骤详解：

  1. 初始化：left = 0, right = n - 1。
  2. 循环条件：当 left < right 时，执行循环。因为需要两个不同的元素，所以指针不能相遇。
  3. 计算当前和：current_sum = nums[left] + nums[right]。
  4. 比较与移动：
    • 情况 A：如果 current_sum == target，我们找到了答案，直接返回 [left + 1, right + 1]（因为题目要求索引从1开始）。
    • 情况 B：如果 current_sum < target，说明当前和太小了。为了让和变大，我们必须增大其中一个加数。由于数组是升序的，nums[left] 已经是最小值（在当前候选范围内），所以唯一能变大的操作是将左指针 left 向右移动一位（left++），以选择一个更大的 nums[left]。
    • 情况 C：如果 current_sum > target，说明当前和太大了。为了让和变小，我们必须减小其中一个加数。nums[right] 已经是最大值，所以唯一能变小的操作是将右指针 right 向左移动一位（right--），以选择一个更小的 nums[right]。
  5. 重复步骤3和4，直到找到答案。

第四步：算法正确性证明（循环不变式思想）

为了让你彻底信服，我们用“循环不变式”来解释：

  • 不变式：在每一次循环开始时，对于任何索引 i < left 或 j > right 的元素，它们不可能是最终解的一部分。
  • 初始化：在第一次循环前，left=0, right=n-1。范围外的集合为空，不变式自然成立。
  • 保持：
    • 若和等于target，算法终止并给出正确解。
    • 若和小于target，对于当前 left，任何与 right 及 right 左边元素（因为它们更小或等于）的配对，和只会更小，所以 nums[left] 不可能与它们组成解。因此我们可以安全地将 left 右移，不变式得以保持。
    • 若和大于target，对于当前 right，任何与 left 及 left 右边元素（因为它们更大或相等）的配对，和只会更大，所以 nums[right] 不可能与它们组成解。因此我们可以安全地将 right 左移，不变式得以保持。
  • 终止：由于每次循环至少移动一个指针，范围 [left, right] 不断缩小。题目保证有解，所以循环必然在 left < right 的某一步终止于 current_sum == target。

第五步：示例推演（以 nums = [2, 7, 11, 15], target = 9 为例）

  1. 初始：left=0 (值2), right=3 (值15)。和=17 > 9。
  2. 和太大，right--：left=0 (2), right=2 (11)。和=13 > 9。
  3. 和太大，right--：left=0 (2), right=1 (7)。和=9 == 9。
  4. 找到答案，返回 [left+1, right+1] = [1, 2]。

第六步：复杂度分析

  • 时间复杂度：O(n)。最坏情况下，两个指针从两端移动到中间，总共遍历了 n 个元素，每次操作是常数时间。
  • 空间复杂度：O(1)。只使用了固定的额外空间（两个指针变量）。

第七步：边界条件与讨论

  1. 输入保证有解：如果题目没有此保证，循环终止条件可以是 left <= right，并在循环结束后返回一个表示未找到的值（如空数组）。
  2. 索引从0还是1开始：根据题目要求灵活调整返回结果。
  3. 数组元素可能为负数或零：该算法依然有效，因为排序性质是关键，数值正负不影响双指针的移动逻辑。

总结

这道题展示了如何巧妙地利用数据的有序性，将看似需要 O(n²) 时间的问题优化到 O(n)。双指针法是处理已排序数组相关问题（如两数之和、三数之和、移除元素等）的经典技巧，其核心在于通过比较和与目标值的关系，确定性地排除不可能的解，从而大幅减少搜索空间。

排序算法之：利用“双指针法”对“已排序数组中的两数之和”问题进行高效求解 题目描述 给定一个 已经按升序排列 的整数数组 nums ，以及一个目标值 target 。请你找出数组中两个不同的元素，使得它们的和等于 target ，并返回这两个元素的 索引 （通常假设索引从 1 开始）。题目保证 有且只有 一个有效答案。 例如： 输入： nums = [2, 7, 11, 15] , target = 9 输出： [1, 2] (因为 nums[1] + nums[2] = 2 + 7 = 9 ) 本题的核心在于利用数组 已排序 的特性，设计出比暴力枚举更高效的算法。 解题过程 第一步：暴力解法分析（作为起点和对比） 最直观的想法是使用两层循环，枚举所有可能的数对 (i, j) （其中 i < j ），检查它们的和是否为 target 。 时间复杂度 ：O(n²)，其中 n 是数组长度。 空间复杂度 ：O(1)。 这种方法没有利用数组已排序的性质，效率低下，但思路简单，有助于我们理解问题。 第二步：引入关键观察——已排序数组的性质 由于数组是 升序排列 的，数组中的元素具有以下性质： 如果固定一个较小的数 nums[i] ，那么要想和达到 target ，另一个数必须是一个较大的数 nums[j] 。 当我们从数组的两端同时向中间遍历时，可以通过比较当前和与 target 的大小关系， 智能地移动指针 ，从而避免不必要的枚举。 第三步：设计双指针算法 我们定义两个指针： 左指针 left ：初始指向数组的第一个元素（最小元素），索引为 0。 右指针 right ：初始指向数组的最后一个元素（最大元素），索引为 n - 1 。 算法步骤详解 ： 初始化 ： left = 0 , right = n - 1 。 循环条件 ：当 left < right 时，执行循环。因为需要两个不同的元素，所以指针不能相遇。 计算当前和 ： current_sum = nums[left] + nums[right] 。 比较与移动 ： 情况 A ：如果 current_sum == target ，我们找到了答案，直接返回 [left + 1, right + 1] （因为题目要求索引从1开始）。 情况 B ：如果 current_sum < target ，说明当前和太小了。为了让和变大，我们必须 增大其中一个加数 。由于数组是升序的， nums[left] 已经是最小值（在当前候选范围内），所以唯一能变大的操作是 将左指针 left 向右移动一位 （ left++ ），以选择一个更大的 nums[left] 。 情况 C ：如果 current_sum > target ，说明当前和太大了。为了让和变小，我们必须 减小其中一个加数 。 nums[right] 已经是最大值，所以唯一能变小的操作是 将右指针 right 向左移动一位 （ right-- ），以选择一个更小的 nums[right] 。 重复步骤3和4，直到找到答案。 第四步：算法正确性证明（循环不变式思想） 为了让你彻底信服，我们用“循环不变式”来解释： 不变式 ：在每一次循环开始时，对于任何索引 i < left 或 j > right 的元素，它们 不可能 是最终解的一部分。 初始化 ：在第一次循环前， left=0 , right=n-1 。范围外的集合为空，不变式自然成立。 保持 ： 若和等于 target ，算法终止并给出正确解。 若和小于 target ，对于当前 left ，任何与 right 及 right 左边元素（因为它们更小或等于）的配对，和只会更小，所以 nums[left] 不可能与它们组成解。因此我们可以安全地将 left 右移，不变式得以保持。 若和大于 target ，对于当前 right ，任何与 left 及 left 右边元素（因为它们更大或相等）的配对，和只会更大，所以 nums[right] 不可能与它们组成解。因此我们可以安全地将 right 左移，不变式得以保持。 终止 ：由于每次循环至少移动一个指针，范围 [left, right] 不断缩小。题目保证有解，所以循环必然在 left < right 的某一步终止于 current_sum == target 。 第五步：示例推演（以 nums = [2, 7, 11, 15] , target = 9 为例） 初始： left=0 (值2), right=3 (值15)。和=17 > 9。 和太大， right-- ： left=0 (2), right=2 (11)。和=13 > 9。 和太大， right-- ： left=0 (2), right=1 (7)。和=9 == 9。 找到答案，返回 [left+1, right+1] = [1, 2] 。 第六步：复杂度分析 时间复杂度 ：O(n)。最坏情况下，两个指针从两端移动到中间，总共遍历了 n 个元素，每次操作是常数时间。 空间复杂度 ：O(1)。只使用了固定的额外空间（两个指针变量）。 第七步：边界条件与讨论 输入保证有解 ：如果题目没有此保证，循环终止条件可以是 left <= right ，并在循环结束后返回一个表示未找到的值（如空数组）。 索引从0还是1开始 ：根据题目要求灵活调整返回结果。 数组元素可能为负数或零 ：该算法依然有效，因为排序性质是关键，数值正负不影响双指针的移动逻辑。 总结 这道题展示了如何巧妙地利用数据的有序性，将看似需要 O(n²) 时间的问题优化到 O(n)。 双指针法 是处理已排序数组相关问题（如两数之和、三数之和、移除元素等）的经典技巧，其核心在于通过比较和与目标值的关系， 确定性地排除不可能的解 ，从而大幅减少搜索空间。