专题 01数组与双指针

1.1为什么数组是所有题的起点

在动手写任何算法之前，先把「数组」这件事想清楚，后面很多优化思路都会自己冒出来。 数组在内存里是一段连续的空间，这个「连续」带来了两个对你刷题至关重要的性质。

性质一：随机访问是 O(1)

因为内存连续，数组里第 i 个元素的地址 = 起始地址 + i × 每个元素大小， 是一次加法算出来的，跟你数组有多长无关。也就是说：

int x = nums[i];   // 无论 nums 有 10 个还是 10 万个元素，这一步都只花固定时间

反例：链表要拿第 i 个元素，得从表头一个个数过去，O(n)。所以「能随机访问」这件事， 让很多「我要看某个位置的数」的操作变得几乎免费。双指针之所以能在数组上玩出花， 根基就是「移动指针、读当前位置」都是 O(1)。

性质二：可以原地（in-place）操作

数组的元素直接躺在内存里，你改 nums[i] 就是真的改了那块内存，不需要新建一个数组。 这带来一个超级实用的结论：很多「整理数组」的题（把某些元素挪前面、删掉某些元素、去重）， 都可以用「两个指针在同一个数组上互相配合、边读边写」完成，空间复杂度压到 O(1)。

降复杂度的直觉：少遍历一遍

绝大多数「数组题为什么能用双指针」的答案，归根结底是一句话：原来的暴力解里，有些遍历是重复的、可以合并的。

举个例子（先不用写代码，建立直觉）：要找数组里两个数加起来等于某个 target。 最朴素的想法是「对每个数，再扫一遍后面所有数看有没有配对的」——两层循环，O(n²)。 但这两层循环里，i 和 j 都在从左往右扫，很多组合被反复查看。如果我们让两个指针一个从左、一个从右， 利用「数组有序」或者「用哈希记住见过谁」，就能把第二层循环整个省掉，变成 O(n)。 所谓双指针，本质就是「让两个下标协同前进，替代一团乱麻的嵌套循环」。

1.2双指针的三种形态

双指针不是一种固定写法，而是一类思想。面试和刷题里，它最常见的有三种长相。 先认脸，后面做题时你才能对上号。

形态一：对撞指针（左右往中间夹）

两个指针 left 和 right 分别站在数组两端，根据条件决定「谁往中间走一步」，直到相遇。

int left = 0, right = n - 1;
while (left < right) {
    // 根据 nums[left] 和 nums[right] 的关系，移动其中一边
    if (应该左走) left++; else right--;
}

典型题：盛最多水的容器、两数之和（有序版）、验证回文串、三数之和的内层。

形态二：快慢指针（同向，一快一慢）

两个指针从同一端出发，fast 走得快（负责「探路」、遍历所有元素），slow 走得慢（负责「记录结果该写哪」）。 slow 永远指向「已经处理好的区间的下一个位置」。

int slow = 0;
for (int fast = 0; fast < n; fast++) {
    if (符合条件) {
        nums[slow] = nums[fast]; // 把 fast 看到的好东西搬到 slow
        slow++;
    }
}

典型题：移动零、删除有序数组中的重复项。这种写法也常叫「覆盖式双指针」。

形态三：固定一个，枚举另一个（三数之和式）

外层固定一个下标 i（当作三元组的「第一个数」），内层用对撞指针在 i 右边找另外两个数。 它是「枚举 + 对撞」的组合，专门处理「找 k 个数之和」这类题（k=3 最常见）。

for (int i = 0; i < n; i++) {
    int left = i + 1, right = n - 1;   // 固定了 i，在它右边用对撞指针
    while (left < right) {
        // 看 nums[i] + nums[left] + nums[right] 与目标的关系，移动左右
    }
}

典型题：三数之和、四数之和、最接近的三数之和。

1.3移动零（简单，力扣 283）

简单 核心：快慢指针覆盖式搬运

题意：给一个数组，把所有 0 移到末尾，非零元素的相对顺序保持不变。 要求原地修改（不能新建数组），函数返回 void。 例：输入 [0,1,0,3,12]，原地变成 [1,3,12,0,0]。

思路推导

第一步，先允许用额外空间。如果可以新建数组，思路太简单了：扫一遍，把非零元素依次放进新数组前部， 剩下的位置补 0。时间 O(n)，空间 O(n)。题目要求原地，所以我们要把这个「新数组」的概念， 映射到原数组自身上。

第二步，观察「非零在前、零在后」意味着什么。其实我们根本不需要关心零去哪—— 只要保证「所有非零元素按原顺序占据数组最前面的位置」，剩下的位置自然全是零。 于是问题变成：如何把非零元素紧凑地排到前面？

第三步，这就是快慢指针。让 fast 当探路者从左到右扫，slow 指向「下一个非零该放的位置」。 fast 每遇到一个非零，就把它搬到 slow 那里，然后 slow 前进一格。 遍历结束后，[0, slow) 就是全部非零元素（顺序和原来一致），[slow, n) 补零即可。

遍历完 slow=3，前 3 个已是非零 [1,3,12]，下标 3、4 补零得到 [1,3,12,0,0]。 为什么顺序不变？因为 fast 和 slow 都从左往右走，非零元素按出现顺序被依次抄到前面，相对次序天然保持。

参考代码（覆盖式 + 末尾补零）

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;                      // slow 指向下一个非零元素应放的位置
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {         // fast 遇到非零元素
                nums[slow] = nums[fast];   // 把它搬到 slow 指向的位置
                slow++;                    // 非零区间向右扩一格
            }
        }
        // 此时 [0, slow) 是原数组的全部非零元素（顺序不变）
        for (int i = slow; i < nums.length; i++) {
            nums[i] = 0;                   // 剩余位置全部填 0
        }
    }
}

复杂度

O(n) 时间（最多遍历两遍），O(1) 空间（只用两个指针变量）。

1.4删除有序数组中的重复项（简单，力扣 26）

简单 核心：快慢指针 + 有序性

题意：给定已按非严格递增排序的数组，原地删除重复出现的元素，使每个元素只出现一次， 返回删除后数组的新长度 k。力扣会根据你返回的 k 取前 k 个元素来判等。 例：输入 [1,1,2]，返回 2，前两个元素应为 [1,2]。

思路推导

第一步，暴力想法为什么行不通。数组不能「真删除」一个元素（那会让后面全体前移，O(n) 且破坏下标）。 题目允许的「删除」其实是覆盖：把不重复的元素往前挪，盖掉重复的。

第二步，利用「有序」。因为数组已排序，重复的元素一定相邻。 这意味着：只要「当前元素和上一个保留下来的元素不同」，它就是一个该保留的新值； 否则它就是重复的，可以忽略。这个「上一个保留下来的元素」由 slow 指着。

第三步，和移动零是同一个模板。移动零是「把非零往前搬」，这里是「把与前一个不同的往前搬」。 slow 指向「已去重区间的末尾」。从第 2 个元素（fast=1）开始，一旦 nums[fast] != nums[slow]， 就把 slow 先 +1 再写入 nums[fast]。第 1 个元素 nums[0] 永远保留（它一定是某值的第一个出现）。

结束后 slow=2，长度返回 slow + 1 = 3，前 3 个元素 [1,2,3]，正确。

参考代码

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;     // 空数组特判，否则下面 nums[0] 会越界
        int slow = 0;                        // [0, slow] 是已去重好的区间，首元素必保留
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {  // 遇到和 slow 不同的新值
                slow++;                      // 去重区间扩一格
                nums[slow] = nums[fast];     // 接到区间末尾
            }
        }
        return slow + 1;                     // 长度 = 末尾下标 + 1
    }
}

复杂度

O(n) 时间（一遍遍历），O(1) 空间。注意这题必须依赖输入有序；若无序，重复项不相邻，此模板失效（那种情况要用哈希，见 专题 02）。

1.5盛最多水的容器（中等，力扣 11）

中等 核心：对撞指针 + 贪心移动

题意：数组 height 竖着画成 n 根柱子，height[i] 是第 i 根的高度。 选两根柱子 i < j 当容器两边，能装的水面积 = min(height[i], height[j]) × (j - i)。 求最大面积。 例：[1,8,6,2,5,4,8,3,7]，最大是 49（选索引 1 和 8：min(8,7)×7 = 49）。

思路推导

第一步，暴力。枚举所有 (i, j) 对，算面积取最大，O(n²)。n 到 10⁵ 必超时。

第二步，关键观察。面积由两件事决定：宽度 j - i 和短板高度 min(h[i], h[j])。 既然宽度最大也就是两端（left=0, right=n-1），我们不妨从最宽的区间出发，然后往里收缩， 看能不能在宽度变小的同时，靠更高的柱子把面积补回来。

第三步，移动哪边？这是本题灵魂。当前区间 [left, right]，面积受限于较矮的那根（短板）。 假如移动较高的那根：宽度必然减小 1，而新高度顶多等于原来的短板（因为短板没动，新柱子再高也被它卡住）， 所以面积一定不会变大，纯属浪费。因此：只有移动较矮的那根，才可能为面积带来提升。 移动矮的，相当于在「当前这根矮柱子能参与的所有区间里，宽度最大的那个已经算过了，更窄的都不可能更优」，于是放心丢弃当前矮指针。

第四步，证明意识（避免「是不是漏解」的担心）。固定 left 不动、right 从最右往左移的每一步， 都是在枚举「以 left 为左端、不同右端」的区间。其中宽度最大的就是 right 最右时。 如果此时 left 是短板，那么以 left 为左端、任何更窄的区间，高度上限都不变（还是被 left 卡住）、宽度更小， 面积必更小，全部可以丢弃。所以「矮了就移动它」不会漏掉更优解。这正是 1.7 节要强调的「移动条件的证明意识」。

参考代码

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int ans = 0;
        while (left < right) {
            int h = Math.min(height[left], height[right]); // 取较矮的柱子作为水面高度
            ans = Math.max(ans, h * (right - left));        // 更新历史最大面积
            if (height[left] < height[right]) {
                left++;   // 左边是短板，移动左指针，期待遇到更高的柱子
            } else {
                right--;  // 否则右边是短板（含相等时随便动哪边都行），移动右指针
            }
        }
        return ans;
    }
}

复杂度

O(n) 时间（左右指针各走一遍，共 O(n) 步），O(1) 空间。这是「对撞指针 + 贪心」的典范。

1.6三数之和（中等，力扣 15）

中等 核心：排序 + 固定一数 + 对撞

题意：给定数组 nums，找出所有不重复的三元组 [a, b, c] 使 a + b + c = 0， 返回 List<List<Integer>>。 例：nums = [-1,0,1,2,-1,-4]，输出 [[-1,-1,2], [-1,0,1]]（顺序不限，但每组内不重复、组间不重复）。

思路推导

第一步，暴力 + 哈希。最直白：三层循环枚举三元组 O(n³)，还得去重。优化一层：固定 a， 在剩余部分用「两数之和」的哈希思路找 b + c = -a，复杂度降到 O(n²)。但哈希去重非常麻烦—— 哈希只能保证数值配对，没法优雅地保证「三元组不重复」。于是转向排序 + 双指针对撞，去重顺手解决。

第二步，排序是前提。先 Arrays.sort(nums)。排序后我们能做两件事： ① 内层用对撞指针在 i 右侧找 b + c = -nums[i]（O(n)）； ② 相同数值相邻，去重只要「跳过相邻的相同值」。

第三步，外层固定 i，内层对撞。外层 i 从 0 到 n-3，把 nums[i] 当 a； left = i+1, right = n-1，看 nums[left] + nums[right] 与 -nums[i] 的关系： 和太小则 left++，太大则 right--，相等就收集。

第四步，去重（本题真正的坑）。要求「不重复的三元组」，不是「不重复的下标」。两层去重：

• 外层去重：if (i > 0 && nums[i] == nums[i-1]) continue;。因为 i 从左往右走， 若当前 a 和上一个 a 相同，那「以这个 a 为起点能配出的所有三元组」上一轮已经全部找过了，重做只会重复，直接跳过。
• 内层去重：找到一组后，left 和 right 各自向内跳过所有等于当前值的数 （while (left < right && nums[left] == nums[left+1]) left++; 同理右边）， 避免同一数值被重复计入。跳完再 left++; right--; 收拢到下一对不同值。

参考代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);                       // 第一步：排序，对撞和去重都依赖有序
        for (int i = 0; i < nums.length - 2; i++) {
            // 外层去重：当前 a 和上一个 a 相同，跳过（上一轮已穷尽它的所有搭配）
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.length - 1;
            int target = -nums[i];               // 要在右边找 b + c = -a
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    res.add(Arrays.asList(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 < target) {
                    left++;                      // 和太小，左指针右移增大
                } else {
                    right--;                     // 和太大，右指针左移减小
                }
            }
        }
        return res;
    }
}

复杂度

排序 O(n log n) + 外层 n 次、每次内层 O(n)，总 O(n²) 时间，O(1) 额外空间（排序一般算原地，结果列表不计）。

1.7本专题常见坑

1.8自测题