【LeetCode系列】双指针解题技巧及例题讲解

WEBSITE：https://www.jessieontheroad.com/

GitHub：https://github.com/Jessie-jzn

双指针核心思想

通过两个指针指向不同的位置，利用它们之间的相对移动来缩小问题规模，从而减少不必要的遍历操作。

💡

✨有序性要求：双指针常用于有序数据，但某些场景（如左右遍历）也可以用于无序数组。

解题思路

明确问题是否适合双指针：

▪️两个数或多个数满足特定条件（如和、差、乘积等）

▪️子数组、子区间问题（如滑动窗口、区间和）

▪️需要优化嵌套循环

排序（必要时）：双指针常用于排序后的数组，因为排序后数据的性质可以加速指针移动。

初始化指针：

▪️左右指针（如一个从头，一个从尾）

▪️快慢指针（如一个快一步，一个慢一步）

根据条件移动指针：

▪️如果条件未满足，调整指针位置（如向内收缩、向前推进）

▪️确保终止条件正确

LeetCode经典例题

125.验证回文串 easy

167. 两数之和 II - 输入有序数组 medium

15. 三数之和 medium

11. 盛最多水的容器 medium

42. 接雨水 hard

典型场景及时间复杂度分析

左右双指针（判断数组中两数之和是否为目标值）

场景：解决有序数组、区间问题或对称性问题

复杂度：指针从两端向中间移动，每个元素最多被访问一次，时间复杂度为O(n)


/**
问题：
给定一个升序数组和目标值，找出两个数使得它们的和等于目标值。
思路：
	1.	初始化两个指针：left = 0, right = nums.length - 1。
	2.	计算当前和：
	•	如果和小于目标值，左指针右移以增大和。
	•	如果和大于目标值，右指针左移以减小和。
	3.	返回结果。
**/
function twoSum(nums, target) {
  let left = 0, right = nums.length - 1;

  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    else if (sum < target) left++;
    else right--;
  }

  return [];
}

快慢双指针（判断链表是否有环）

场景：用于链表中的循环检测、删除重复元素等

复杂度：慢指针通常每次移动一步，快指针每次移动两步，总体遍历的复杂度为O(n)


/**
问题：
将数组中的所有 0 移动到末尾，同时保持非零元素的相对顺序。
思路：
	1.	用快慢指针。
	•	慢指针 记录非零元素应该放置的位置。
	•	快指针 遍历数组。
	2.	遇到非零元素时，交换快慢指针所在位置的值。
**/
function moveZeroes(nums) {
  let slow = 0;

  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
      slow++;
    }
  }
}

滑动窗口（变种双指针）（求和等于目标值的子数组长度）

场景：求解满足条件的连续子数组或子字符串

复杂度：窗口的左指针和右指针都移动，整体最多移动2n步，时间复杂度为O(n)


/**
问题：
找到一个字符串中包含所有目标字符的最小子串。
思路：
	1.	用左右指针构造一个滑动窗口。
	2.	调整窗口大小以满足条件：
	•	如果窗口满足条件，尝试缩小窗口。
	•	如果窗口不满足条件，扩大窗口。
**/
function minWindow(s, t) {
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);

  let left = 0, right = 0, valid = 0, minLen = Infinity, start = 0;
  const window = new Map();

  while (right < s.length) {
    const c = s[right];
    right++;

    if (need.has(c)) {
      window.set(c, (window.get(c) || 0) + 1);
      if (window.get(c) === need.get(c)) valid++;
    }

    while (valid === need.size) {
      if (right - left < minLen) {
        start = left;
        minLen = right - left;
      }

      const d = s[left];
      left++;

      if (need.has(d)) {
        if (window.get(d) === need.get(d)) valid--;
        window.set(d, window.get(d) - 1);
      }
    }
  }

  return minLen === Infinity ? "" : s.slice(start, start + minLen);
}

嵌套循环优化（三数之和问题）

场景：解决三数之和或矩形覆盖问题。

复杂度：内层循环的范围因为双指针优化而缩小，例如三数之和中，外层循环为O(n)，内层双指针部分为O(n)，总复杂度为O(n^2)

前端应用

实现分页和滚动加载：双指针可以用来检测页面的滚动位置（如一个指针表示用户的视口位置，另一个指针表示数据源中的位置），从而动态加载数据

滑动窗口算法：比如在实现实时数据流（如股票价格、传感器数据等）的处理时，使用双指针滑动窗口技术可以帮助计算窗口内的特定统计信息

例题讲解：三数之和

题目：

给一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：


输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

问题解析：

目标：找到所有数组中不重复的三元组，使得它们的和为0。

输入：一个整数数组 nums。

输出：所有符合条件的三元组，结果不能包含重复。

解题思路

1. 排序数组

排序让我们可以利用数组的顺序性，从小到大地进行查找，避免重复。


nums.sort((a, b) => a - b);
// 排序后：[-4, -1, -1, 0, 1, 2]

2. 固定一个数，寻找其他两数

假设当前固定的数是 nums[i]，那么目标就是找到两个数 nums[left] 和 nums[right]，使得：nums[i] + nums[left] + nums[right] = 0

我们用两个指针 left 和 right 分别从 i + 1 和数组末尾开始移动

3. 核心逻辑

判断三数之和

如果 nums[i] + nums[left] + nums[right] === 0，就把它们加入结果

如果和小于 0，说明需要更大的数，让 left++

如果和大于 0，说明需要更小的数，让 right--

避免重复

如果当前数字和前一个数字相同（nums[i] === nums[i-1]），直接跳过

找到一个答案后，需要跳过重复的数字，分别调整 left 和 right

4. 算法伪代码

以输入 nums = [-4, -1, -1, 0, 1, 2] 为例，逐步解释

1.排序数组：[-4, -1, -1, 0, 1, 2]。

2.遍历数组，依次固定一个数：

固定 nums[0] = -4

左右指针：left = 1, right = 5。
当前和：nums[0] + nums[1] + nums[5] = -4 + -1 + 2 = -3，小于 0，移动 left
当前和：nums[0] + nums[2] + nums[5] = -4 + -1 + 2 = -3，继续移动 left
结果：没有满足条件的组合。

固定 nums[1] = -1：

左右指针：left = 2, right = 5。
当前和：nums[1] + nums[2] + nums[5] = -1 + -1 + 2 = 0，找到答案 [-1, -1, 2]
跳过重复，调整指针 left = 3, right = 4
当前和：nums[1] + nums[3] + nums[4] = -1 + 0 + 1 = 0，找到答案 [-1, 0, 1]

固定 nums[2] = -1:

因为 nums[2] === nums[1]，跳过重复。

固定 nums[3] = 0：

左右指针：left = 4, right = 5。
当前和：nums[3] + nums[4] + nums[5] = 0 + 1 + 2 = 3，大于 0，移动 right。
结果：没有满足条件的组合。

完整代码


var threeSum = function(nums) {
    nums.sort((a, b) => a - b); // 先排序
    const result = [];

    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue; // 避免固定数重复

        let left = i + 1, right = nums.length - 1;

        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            if (sum === 0) {
                result.push([nums[i], nums[left], nums[right]]);
                while (left < right && nums[left] === nums[left + 1]) left++; // 跳过重复
                while (left < right && nums[right] === nums[right - 1]) right--; // 跳过重复
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }

    return result;
};

复杂度分析

时间复杂度：

排序：O(nlogn)

双指针：每次O(n)，外层遍历O(n)，总计O(n^2)

空间复杂度：O(1)

如何联想到双指针法解题思路？

1. 识别问题特性

在看到问题时，要敏锐地抓住问题的特性

比如三数之和问题有以下特点：

需要找到多个数的组合

要满足特定条件（三数之和为 0）

输出要求不重复的结果。

💡

怎么联想到双指针？

求和问题通常可以排序：

排序是解决很多问题的第一步，尤其是涉及数值范围的题目

排序的好处：

可以将问题转化为区间问题（通过调整指针来缩小范围）

能更容易避免重复，因为相同的数会相邻

组合问题常用递进的方式：

当需要从一组数中选出多组组合时，可以固定一个元素，然后让程序处理剩下的部分。固定一个数后，剩下的问题就变成了两数之和的简单版本。

双指针法特别适合有序数组：

排序后，可以使用左右指针从两端逼近，快速找到答案

2. 将暴力法优化为双指针

如果在一开始想不到双指针法，可以先用暴力法思考：

暴力法的核心是三层嵌套循环，每次选出三个数

时间复杂度O(n^3)是无法接受的，所以需要优化。

优化过程的思路：

1.暴力法冗余在哪？

暴力法中，我们对数组的每三个元素进行无脑组合，其中有许多重复的计算

比如，选了 nums[i] 后，再遍历剩下两数时，暴力法没有利用任何规律。

2.可以省掉的部分

当数组是有序的，我们知道如果当前和太小，可以通过增加最小值让和变大。

同理，如果和太大，可以通过减小最大值让和变小。

这就是双指针的核心优化。

3. 学会分解问题

解决三数之和问题时，不要试图一口气解决所有部分，而是分步骤：

1.处理单一条件：

首先处理重复数字的问题（如何跳过相同的 nums[i]）。

固定一个数后，剩下的问题是否可以用更简单的逻辑解决？

2.解决局部问题：

固定一个数后，剩下的部分转化为一个简单的两数之和问题。

4. 思考如何避免重复

如果发现问题要求结果唯一，这就提示需要注意 如何去重。

双指针法的好处之一就是可以轻松避免重复：

数组排序后，相同数字会相邻。

当遇到重复的数时，直接跳过当前指针，避免重复计算。

5. 多做相关类型的题

双指针法 是算法中的一种通用技巧，多做一些经典题目会帮助培养直觉。例如：

简单题型：

两数之和（Two Sum）【最基础的变种】

反转字符串（Reverse String）

移动零（Move Zeroes）

进阶题型：

盛最多水的容器（Container With Most Water）

四数之和（4Sum）

有序数组的交集（Intersection of Two Arrays II）

回溯和动态规划结合双指针：

最长回文子串（Longest Palindromic Substring）

字符串的滑动窗口问题（Sliding Window Maximum）

6. 培养”逐步优化”的算法思维

从简单的暴力法入手：

写出最简单但可能效率低的代码

找到低效点：

分析代码的瓶颈，比如：

•是否有多余的计算？

•是否有重复检查？

利用问题特点优化：

数组有序 -> 双指针

使用哈希表 -> 提高查找效率

动态规划 -> 存储中间结果。

7. 示例：如何从暴力法进化到双指针

暴力法

用三层嵌套循环找到所有三元组：


var threeSum = function(nums) {
  const result = [];
  for (let i = 0; i < nums.length - 2; i++) {
    for (let j = i + 1; j < nums.length - 1; j++) {
      for (let k = j + 1; k < nums.length; k++) {
        if (nums[i] + nums[j] + nums[k] === 0) {
          result.push([nums[i], nums[j], nums[k]]);
        }
      }
    }
  }
  return result;
};

问题：

每三个数都要组合，复杂度是O(n^3)

没有考虑重复的问题

优化为双指针

1.排序数组，避免重复。

2.固定 nums[i] 后，用双指针查找其他两个数：


var threeSum = function(nums) {
  nums.sort((a, b) => a - b); // 排序
  const result = [];

  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue; // 跳过重复
    let left = i + 1, right = nums.length - 1;

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        while (left < right && nums[left] === nums[left + 1]) left++; // 跳过重复
        while (left < right && nums[right] === nums[right - 1]) right--;
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }
  return result;
};

8. 如何培养直觉

理解排序的意义：当数组排序后，很多问题可以变成区间问题

理解双指针法的精髓：一边移动，另一边固定，通过调整来逐步缩小范围

多练习经典题型：多刷题，逐渐形成模式识别能力