← 课程目录 🚀 从零到一
📐 学习维度 阶段8 · 第32章 数据结构与算法专题(leetcode 分类刷题指南) 🚀 从零到一 📚 课程目录 🏠 首页 🛤️ 学习路径

32.1 数组与双指针:手撕代码的第一道关

审校 2026-09-29 · 素材来源:raw 50 必刷题单复盘、ideaProject/leetcode
📑 本篇章节导航 (共10节,点击直达)
场景:为什么数组题是第一关类比与定义:双指针是什么最小可跑示例:盛最多水的容器原理拆解:数组题四大套路Kadane 变体与套路边界复杂度速查:数组四大套路对照追问链演示:三数之和的现场踩坑清单面试怎么问一句话总结

算法章第一讲从数组开始。面试官让手撕代码时,数组题出现得最早也最频繁——它不需要额外数据结构,考的纯粹是思路与边界。这一讲按必刷题单的数组线(LeetCode 1、11、15、53、56)拆双指针与子数组两大套路,每题给「最小可跑版本」与追问预案。

场景:为什么数组题是第一关

现场手撕通常五到十分钟。面试官抛出「给一个数组,找出……」,你的第一反应决定印象分:先问数据范围与特性(有没有序、有没有负数、数据量多大),再选解法。数据量一万还用 O(n²) 双重循环,直接暴露没有复杂度意识。数组题的准备工作就一句话:每个套路练到「五分钟内写出无 bug 版本」。

类比与定义:双指针是什么

双指针(用两个下标协同遍历的技巧)像两人搜一条走廊:对撞指针是一人从左、一人从右往中间走,适合有序数组或区间问题;快慢指针是两人同向但速度不同,适合原地去重与链表判环;滑动窗口是两人同向保持一段距离,适合子串子数组(下一讲细讲)。它的本质收益:把两层嵌套循环压成一层,O(n²) 降到 O(n)。

最小可跑示例:盛最多水的容器

LeetCode 11:数组每个元素是垂线高度,两根线与 x 轴围成的容器能装最多水。对撞指针从两端出发,每轮计算面积,然后移动较短的一端:


public int maxArea(int[] h) {
    int l = 0, r = h.length - 1, ans = 0;
    while (l < r) {
        // 面积 = 短板高度 × 宽度
        int area = Math.min(h[l], h[r]) * (r - l);
        ans = Math.max(ans, area);
        if (h[l] < h[r]) l++;   // 移动短板才可能更大
        else r--;               // 移动长板宽度减一,高度仍被短板限制
    }
    return ans;
}

为什么移动短板是对的:移动长板时宽度变小,高度受短板限制不变,面积只可能更小——所以长板那边的情况可以安全丢弃。这个「丢弃论证」就是面试官要追的证明。

原理拆解:数组题四大套路

套路一·对撞指针:两数之和 II(有序版)、验证回文串、三数之和(15)的内层都是它。三数之和的完整解法:排序后固定一个数,剩下用对撞指针找 target,去重靠「跳过相同元素」。套路二·哈希换时间:两数之和(1)无序版用 HashMap 一次遍历,O(n) 换 O(n) 空间——面试官常追问「为什么不能用双指针」:无序数组移动指针没有判断依据。套路三·Kadane 最大子数组和(53):cur = Math.max(num, cur + num) 一行转移,含义是「要么续上前缀,要么从自己重新开始」;追问变体:环形数组、要求返回区间下标。套路四·区间扫描:合并区间(56)先按左端点排序,再一次扫描拼接:


public int[][] merge(int[][] iv) {
    Arrays.sort(iv, (a, b) -> a[0] - b[0]);   // 按左端点排序
    List<int[]> res = new ArrayList<>();
    int[] cur = iv[0];
    for (int i = 1; i < iv.length; i++) {
        if (iv[i][0] <= cur[1])               // 有重叠:拉长右端点
            cur[1] = Math.max(cur[1], iv[i][1]);
        else { res.add(cur); cur = iv[i]; }   // 不重叠:落盘开新区间
    }
    res.add(cur);
    return res.toArray(new int[0][]);
}

Kadane 变体与套路边界

Kadane 的两个高频变体先备好:环形数组版(918)——分「不跨环」与「跨环」两段,后者等于总和减最小子数组和,一句转化就让面试官看到套路的可迁移性;带下标版——维护临时起点,当 cur 被重置时记录新起点,答案更新时一并落盘。再备一个收尾判断:什么题不能用双指针——数组无序且问题与「区间两端」无关时(如求子数组个数),双指针没有单调性可依,老实回哈希或 DP,主动说边界比被问穿强。

复杂度速查:数组四大套路对照

对撞指针:O(n) 时间 O(1) 空间,前提通常是有序;哈希换时间:O(n) 时间 O(n) 空间,代价是额外内存与哈希计算;Kadane:O(n) 时间 O(1) 空间,一次遍历;区间扫描:排序主导 O(n log n),扫描本身 O(n)。看到题先在脑内过一遍这张表:「数据有序吗(对撞可行)、能接受额外空间吗(哈希可行)、是连续区间问题吗(Kadane 或窗口)」——三问定位套路,这就是数组题的审题模板。数组题还有一层隐性考察:复杂度的口头承诺——写之前先说「这是 O(n) 时间 O(n) 空间」,面试官立刻有了参照物;写完才被问复杂度,印象完全不同。

追问链演示:三数之和的现场

「三数之和怎么做」的标准现场是一出五分钟连贯剧。第一步澄清:数组无序、元素可重复、要所有不重复三元组。第二步报思路:排序消除无序性 → 固定一个数,剩下的按两数之和用对撞指针 → 总复杂度 O(n²)。第三步边写边念两处去重:


List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;   // 去重一:固定数
        int l = i + 1, r = nums.length - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (sum < 0) { l++; continue; }
            if (sum > 0) { r--; continue; }
            res.add(Arrays.asList(nums[i], nums[l], nums[r]));
            while (l < r && nums[l] == nums[l + 1]) l++; // 去重二:左跳重
            while (l < r && nums[r] == nums[r - 1]) r--; // 去重三:右跳重
            l++; r--;
        }
    }
    return res;
}

第四步走查:输入 [-1,0,1,2,-1,-4],排序后 [-4,-1,-1,0,1,2]——固定第一个 -1 得 (-1,-1,2) 与 (-1,0,1),正好覆盖两处去重分支。去重的本质:排序让相同值相邻,相邻即跳过,「先排序」在去重上产生复利。若追问四数之和:同框架再固定一层,O(n³)——套路可扩展,这句收尾展示举一反三。

踩坑清单

面试怎么问

一句话总结

数组题的四个套路——对撞指针、哈希换时间、Kadane、区间扫描——每个都配一个「丢弃论证」,面试考的不是背代码,是你说清「为什么这样移动不漏解」。