王大师王文峰头像
Java 算法分层刷题：6 道高频题带「标准答案 + 追问链路 + 踩坑点」【两数之和、LRU、接雨水、单调队列】封面图

Java 算法分层刷题：6 道高频题带「标准答案 + 追问链路 + 踩坑点」【两数之和、LRU、接雨水、单调队列】

✍️ 作者：王文峰（外号：神秘小峯 / 山峯）｜中国国学、传统文化与代码爱好者的程序人生，期待你的关注和支持！

Java 算法分层刷题：6 道高频题带「标准答案 + 追问链路 + 踩坑点」【两数之和、LRU、接雨水、单调队列】

在这里插入图片描述

📚 算法题最大的坑不是"不会做"，而是做完就忘、问深就懵。本文按三层难度精选 6 道 Java 面试最高频题，每题固定三件套：标准答案（可直接跑）→ 追问链路（面试官的连环套怎么接）→ 高频踩坑点（别人挂在这的雷）。刷完这 6 题，哈希、栈、滑动窗口、双指针、单调队列、设计题六大考点全部打通。

一、开篇：为什么要"分层"刷题

层级定位目标用时本篇题目训练目标
L1 入门热身，建立手感20~30 分钟/题两数之和、有效括号哈希表、栈的基本直觉
L2 进阶中频主力40~60 分钟/题最长无重复子串、LRU滑动窗口、设计题套路
L3 高手拉开差距60 分钟+接雨水、滑动窗口最大值双指针证明、单调队列

💡 分层的意义：L1 建立"数据结构直觉"，L2 训练"套路识别"，L3 锻炼"证明与追问"。面试现场 80% 的题在 L2 水平，但决定你过不过的往往是追问环节——这就是每题都要配追问链路的原因。

刷题姿势：先自己想 15~20 分钟 → 再看标准答案 → 隔天盲写。看答案 ≠ 会做，盲写才算掌握。

在这里插入图片描述

二、L1-1：两数之和（哈希表入门）

题目：给定整数数组 nums 和目标值 target，找出和为 target 的两个数的下标，假设恰好一个答案。

标准答案

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();  // 值 -> 下标
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            // 先查再放：避免"自己配自己"
            if (seen.containsKey(need)) {
                return new int[]{seen.get(need), i};
            }
            seen.put(nums[i], i);
        }
        return new int[0];   // 无解返回空数组，别返回 null
    }
}

时间 O(n)，空间 O(n)。

追问链路

追问参考答案
Q1：为什么一遍遍历就够？第 i 个元素只需知道"前面有没有 target-nums[i]“，哈希表 O(1) 查"已见过的值”
Q2：能不能先排序再双指针？可以降到 O(1) 空间，但排序会破坏原始下标，需额外记录 (值,下标) 对
Q3：如果数组有重复值、要返回所有不重复对呢？排序 + 双指针 + 跳过重复值，答案去重
Q4：哈希冲突时复杂度还成立吗？严格说退化为 O(n²)，Java 8 后链表转红黑树，实际可忽略

高频踩坑点

  • ❌ 先 put 再查：[3,3], target=6 会把自己当下标配对；
  • ❌ 暴力两层循环 O(n²) 起手——面试直接减分；
  • ❌ 返回 null，建议返回空数组并说明约定。

三、L1-2：有效的括号（栈入门）

题目：()、[]、{} 视为有效，判断字符串是否全部有效嵌套。

标准答案

class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 != 0) return false;          // 奇数必无效，快速返回
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
        for (char c : s.toCharArray()) {
            if (!pairs.containsKey(c)) {                 // 左括号入栈
                stack.push(c);
            } else {                                     // 右括号：核对栈顶
                if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
                    return false;
                }
            }
        }
        return stack.isEmpty();                          // 最终必须栈空
    }
}

时间 O(n)，空间 O(n)。

追问链路

追问参考答案
Q1：为什么非用栈不可？后进先出匹配"最近未闭合"的括号，这是栈的定义级场景
Q2：只有一种括号能更省吗？用计数器代替栈，O(1) 空间
Q3：进阶——生成所有合法括号组合？回溯：左括号数 < n 时可加左，右括号数 < 左括号数时可加右（经典 LeetCode 22）
Q4：栈用 Stack 还是 ArrayDeque？永远 ArrayDeque，Stack 继承自 Vector，方法全加锁

高频踩坑点

  • ❌ 结束只返回"遍历完了"，忘了 stack.isEmpty()（漏 ((( 这种情况）；
  • ❌ Map.of 只放右括号映射左括号，方向写反；
  • ❌ 用 Vector/Stack，性能与规范双扣分。

四、L2-1：最长无重复子串（滑动窗口）

题目：找出字符串中不含重复字符的最长子串长度。

标准答案

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> last = new HashMap<>();  // 字符 -> 最后出现下标
        int left = 0, max = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            // 关键判断：旧位置必须在窗口内才需要收缩
            if (last.containsKey(c) && last.get(c) >= left) {
                left = last.get(c) + 1;                  // 左边界只增不减
            }
            last.put(c, right);
            max = Math.max(max, right - left + 1);
        }
        return max;
    }
}

时间 O(n)，空间 O(字符集大小)。

追问链路

追问参考答案
Q1：为什么窗口不会"回退"？left 只接收更大的值，窗口单调向右，所以是 O(n) 而非 O(n²)
Q2：定长窗口（长度 k 无重复）怎么改？删掉 left = last.get(c)+1，改为"窗口超 k 就左移"，多一个长度校验
Q3：变体——最长全 1 子数组（最多翻转 K 个 0）？不定长滑动窗口：零数 > K 时收缩左边界
Q4：字符集很大（含中文/Emoji）怎么办？HashMap 换成 int[128]（ASCII）或直接 HashMap<Character,Integer> 兜底

高频踩坑点

  • ❌ 少了 last.get(c) >= left 判断："abba" 里 left 会被旧位置拉回去（经典翻车现场）；
  • ❌ 用 substring + HashSet 每次重建，O(n²) 超时；
  • ❌ 空串返回 -1，正确是 0。

五、L2-2：LRU 缓存（设计题必考）

题目：实现 LRUCache，get/put 均要求 O(1)。

标准答案（标准库 5 行版）

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);   // 第三个参数 accessOrder=true：访问即挪到队尾
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);   // get 会触发 accessOrder 更新顺序
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;              // 超容自动淘汰最久未用
    }
}

追问链路：手写版（面试标准要求）

追问参考答案
Q1：为什么能 O(1)？哈希表 O(1) 查节点 + 双向链表 O(1) 增删挪位，两者缺一不可
Q2：为什么必须双向链表？单链表删除要先找前驱，找前驱 O(n)；双向链表持有 prev 直接删
Q3：边界判断很烦怎么办？哨兵头尾节点（dummy head/tail），所有节点操作统一化
Q4：线程不安全怎么办？Collections.synchronizedMap 或 ConcurrentHashMap + 分段锁；高并发常见"分片 LRU"

手写版完整代码（背这个）：

class LRUCache2 {
    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0), tail = new Node(0, 0);  // 哨兵

    static class Node {
        int key, val;                 // key 必须存！淘汰时靠它从 map 里删
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }

    public LRUCache2(int capacity) {
        this.capacity = capacity;
        head.next = tail; tail.prev = head;
    }

    public int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        moveToHead(n);
        return n.val;
    }

    public void put(int key, int value) {
        Node n = map.get(key);
        if (n == null) {
            n = new Node(key, value);
            map.put(key, n);
            addToHead(n);
            if (map.size() > capacity) {               // 淘汰队尾
                Node removed = removeTail();
                map.remove(removed.key);               // 两处都要删！
            }
        } else {
            n.val = value;
            moveToHead(n);
        }
    }

    private void addToHead(Node n)  { n.prev = head; n.next = head.next; head.next.prev = n; head.next = n; }
    private void removeNode(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
    private void moveToHead(Node n) { removeNode(n); addToHead(n); }
    private Node removeTail()       { Node n = tail.prev; removeNode(n); return n; }
}

高频踩坑点

  • ❌ 忘了 accessOrder=true——写完发现是"纯插入序 LRU"；
  • ❌ 哈希表里存值不存 Node——删除节点时找不到引用，O(1) 变 O(n)；
  • ❌ Node 不存 key——淘汰时不知道该从 map 删哪个键；
  • ❌ 只删链表不删 map（或反之），两处必须同步。

六、L3-1：接雨水（双指针）

题目：给定 n 个非负整数表示柱子高度，计算按此排列的柱子下雨后能接多少雨水。

标准答案

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0, ans = 0;
        while (left < right) {
            if (height[left] < height[right]) {        // 短边决定水量
                leftMax = Math.max(leftMax, height[left]);
                ans += leftMax - height[left];
                left++;
            } else {
                rightMax = Math.max(rightMax, height[right]);
                ans += rightMax - height[right];
                right--;
            }
        }
        return ans;
    }
}

时间 O(n)，空间 O(1)。

追问链路

追问参考答案
Q1：暴力/朴素做法是什么？每个位置 min(左侧最大, 右侧最大) - 当前高度，预处理两个最大值数组，O(n) 空间
Q2：双指针为什么不会漏？某侧柱子矮于另一侧时，它那一侧的 max 已被"更远的边界"锁死，短边的水量只取决于本侧 max，不会受另一侧未来影响
Q3：相等时走哪边？走哪边都对（else 分支），水量一样
Q4：变体——接雨水 II（二维平面）？优先队列（小顶堆）从边界向内推进，每次弹出最低边扩展邻居（LeetCode 407）
Q5：兄弟题？柱状图最大矩形（单调栈，LeetCode 84），面试同样高频

高频踩坑点

  • ❌ 边缘柱子算进水量（边缘不可能积水，正确算法天然为 0）；
  • ❌ 用 Math.max(0, leftMax - h) 打补丁——说明逻辑已经错了，先想清楚再写；
  • ❌ 起手写暴力 O(n²) 却不主动说"可优化到 O(n)"，会错失加分。

七、L3-2：滑动窗口最大值（单调队列）

题目：大小为 k 的窗口从左滑到右，返回每个窗口的最大值数组。

标准答案

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0 || nums.length < k) return new int[0];
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();   // 存【下标】，对应值单调递减

        for (int right = 0; right < n; right++) {
            // 队尾比新元素小的全部出队：它们永远不可能成为最大值
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[right]) {
                dq.pollLast();
            }
            dq.offerLast(right);

            if (right >= k - 1) {                          // 窗口首次形成
                ans[right - k + 1] = nums[dq.peekFirst()]; // 队首即窗口最大
                if (dq.peekFirst() <= right - k) {         // 队首已滑出窗口
                    dq.pollFirst();
                }
            }
        }
        return ans;
    }
}

时间 O(n)（均摊），空间 O(k)。

追问链路

追问参考答案
Q1：为什么队列单调递减？队首永远是"活着的最大值"，比新元素小的旧元素没有存在价值，直接淘汰
Q2：为什么复杂度是 O(n)？每个下标最多入队一次、出队一次，均摊 O(1)——这是单调队列的证明核心
Q3：为什么存下标不存值？靠下标判断"是否滑出窗口"（peekFirst() <= right - k），存值就没法判过期
Q4：堆（优先队列）能做吗？能，O(n log n)，堆顶过期时惰性删除——但打不过单调队列
Q5：变体？窗口大小不固定求最大（不定长）、IPO 求最大利润（双堆）、数据流中位数（大小顶堆对）

高频踩坑点

  • ❌ 队列里存值——过期判断无从下手；
  • ❌ 出队条件写成 < 而非 <=：相等元素残留，队列膨胀、答案可能取到过期元素；
  • ❌ 过期判断放在输出之前：队首可能是刚入队的合法元素，顺序要"先取最大，再清过期"；
  • ❌ 忘了边界：k > n 或 k <= 0 直接返回空数组。

八、六题一图流：数据结构与套路速查

题目核心结构时间一句话套路
两数之和HashMapO(n)"见过什么"用哈希记
有效括号ArrayDeque 栈O(n)"最近未匹配"交给栈
最长无重复子串滑动窗口 + HashMapO(n)不定长窗口：右扩左收
LRUHashMap + 双向链表O(1)查得快靠哈希，删得快靠双链
接雨水双指针O(n)短边决定水量，向内推进
窗口最大值单调队列O(n)没价值的元素提前踢掉

三板斧总结：见到"子串/子数组"想滑动窗口，见到"配对/去过的历史"想哈希或栈，见到"滑动中取最值"想单调队列，见到 O(1) 要求想哈希 + 链表/双指针。

九、刷题方法论：三遍法

  1. 第一遍：裸想 15~20 分钟——没思路就看题解，但要标记"卡点在哪一步"；
  2. 第二遍：精读标准答案——重点看追问链路里的"为什么这么想"，而不是背代码；
  3. 第三遍：隔天盲写——不看答案重写，写完跑用例，卡壳的地方就是没掌握的地方。

💡 加分动作：每题写完主动报复杂度并说一句"还有 XX 优化空间"——这一个动作能让你在面试官眼里从"背题的"变成"懂题的"。

十、总结与自测清单

  • ✅ 两数之和：先查后放，别把自己配给自己；
  • ✅ 有效括号：结束必须 stack.isEmpty()，容器用 ArrayDeque；
  • ✅ 滑动窗口：last.get(c) >= left 是灵魂判断，窗口只进不退；
  • ✅ LRU：哈希存 Node 引用、Node 存 key、链表 map 两处同步；
  • ✅ 接雨水：短边决定水量，能主动讲出双指针正确性证明；
  • ✅ 窗口最大值：单调队列存下标，均摊 O(n) 的证明是"每个元素进出各一次"；
  • ✅ 任何题答完都补一句复杂度与优化方向。

下一篇：《Java 算法分层刷题·动态规划篇》——从爬楼梯到打家劫舍到最长公共子序列，把 DP 的状态定义与转移方程讲透，敬请关注！

🎯 学习教程（传送门）

序号专栏学习内容当前状态
01JAVA从入门到进阶的系统知识持续写作中……
02Oracle数据库从用法到实战创作中……
03vbs脚本手把手教你做脚本完善中……
04IDEA牛逼哄哄的编程利器编写中……
05面试吐血整理的面试技巧更新中……

在这里插入图片描述

🔥 往期文章

🧭 精选往期好文，更多请移步 我的博客主页

在这里插入图片描述

👍 点赞 + ⭐ 收藏 + 💬 评论，一键三连走起！
你们的支持，是我持续创作的最大动力～

在这里插入图片描述

✨ 以上就是今天的全部内容，关注我，技术之路不迷路！

📖 本人详解
✍️ 作者：王文峰，参与 CSDN 2020 年度博客之星评选，《Java王大师王天师》，外号：神秘小峯 / 山峯
🏮 中国国学、传统文化与代码爱好者的程序人生，期待你的关注和支持！
🔗 转载说明：务必注明来源（注明：作者：王文峰哦）

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/Feng_wwf/article/details/168531047

文章来源转载

评论

评论列表

微信小程序
QQ小程序

关于作者

点赞数：0
关注数：0
粉丝：0
文章：0
关注标签：0
加入于：--