LeetCode hot100

数据结构与算法的脑图

• 基础数据结构（必掌握）
  • 数组 & 字符串
    • 核心特性：连续内存、随机访问O(1)、增删O(n)
    • 刷题高频点：双指针、滑动窗口、前缀和、差分、字符串匹配(KMP)
    • 经典题型：两数之和、最长回文子串、滑动窗口最大值
  • 链表
    • 核心特性：非连续内存、顺序访问O(n)、增删O(1)（已知节点）
    • 刷题高频点：虚拟头节点、快慢指针、反转链表、环形链表
    • 经典题型：反转链表、合并两个有序链表、环形链表Ⅱ
  • 栈 & 队列
    • 栈：先进后出（FILO），核心操作push/pop/top
      • 高频场景：括号匹配、单调栈（接雨水、柱状图最大面积）
    • 队列：先进先出（FIFO），核心操作push/pop/front
      • 高频场景：BFS、单调队列（滑动窗口最大值）
    • 经典题型：有效的括号、用栈实现队列、滑动窗口最大值
  • 哈希表（字典/集合）
    • 核心特性：键值对存储、查询/增删O(1)（理想情况）
    • 刷题高频点：哈希映射（计数/去重）、哈希集合（存在性判断）
    • 经典题型：两数之和、字母异位词分组、最长连续序列
• 进阶数据结构（高频考点）
  • 树 & 二叉树
    • 基础概念：根节点、叶子节点、深度/高度、遍历方式
    • 核心遍历：前序/中序/后序（递归+迭代）、层序遍历（BFS）
    • 特殊二叉树：二叉搜索树(BST)、平衡二叉树(AVL)、完全二叉树
    • 经典题型：二叉树的层序遍历、验证二叉搜索树、路径总和
  • 堆（优先队列）
    • 核心特性：完全二叉树、大顶堆/小顶堆、插入/弹出O(logn)
    • 刷题高频点：topK问题、数据流中位数、贪心策略
    • 经典题型：数组中的第K个最大元素、数据流的中位数
  • 图
    • 基础表示：邻接矩阵、邻接表
    • 核心遍历：DFS（深度优先）、BFS（广度优先）
    • 高频算法：最短路径（Dijkstra/Floyd）、并查集（连通性）、拓扑排序
    • 经典题型：岛屿数量、课程表（拓扑排序）、网络延迟时间
  • 单调结构（单调栈/单调队列）
    • 核心思想：维护有序的栈/队列，降低时间复杂度
    • 适用场景：找下一个更大/更小元素、区间最值
    • 经典题型：每日温度、柱状图中最大的矩形、滑动窗口最大值
• 高级数据结构（提升效率）
  • 并查集（Disjoint Set Union, DSU）
    • 核心操作：查找(find)、合并(union)、路径压缩、按秩合并
    • 适用场景：连通性问题、分组问题
    • 经典题型：朋友圈、冗余连接、岛屿数量（进阶）
  • 前缀树（Trie树）
    • 核心特性：字符串前缀存储、高效查询前缀/单词
    • 适用场景：单词搜索、前缀匹配
    • 经典题型：实现Trie树、单词搜索Ⅱ
  • 线段树 & 树状数组
    • 线段树：区间查询、区间更新O(logn)，适用复杂区间操作
    • 树状数组：单点更新、前缀和查询O(logn)，适用简单区间操作
    • 经典题型：区域和检索 - 数组可修改、逆序对的数量
  • 哈希集合/映射进阶
    • 布隆过滤器：海量数据存在性判断（有一定误判率）
    • LRU缓存：最近最少使用，哈希表+双向链表实现
    • 经典题型：LRU缓存、LFU缓存
• 刷题策略 & 技巧
  • 按类型刷题：先刷基础结构，再攻进阶结构
  • 高频技巧：双指针、贪心、二分查找、递归/回溯、动态规划
  • 复杂度分析：时间复杂度（重点）、空间复杂度（优化方向）
  • 易错点：边界条件（空值、单元素）、索引越界、重复计算

数组

53. 最大子数组和

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
  
class Solution {
    public int maxSubArray(int[] nums) {
        int preSum =0,maxAns = nums[0];
        for(int x:nums){
            preSum = Math.max(preSum+x,x);
            maxAns = Math.max(maxAns,preSum);
        }
        return maxAns;
        
    }
}

56. 合并区间

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
示例 3：

输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。
  
class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length ==0){
            return new int[0][2];
        }

        Arrays.sort(intervals,new Comparator<int[]>(){
            public int compare(int[] interval1,int[] interval2){
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for(int i=0;i<intervals.length;i++){
            int L=intervals[i][0],R= intervals[i][1];
            // [1,3] [4,5] 当3<4 直接添加
            if(merged.size()==0 ||merged.get(merged.size()-1)[1]<L){
                merged.add(new int[]{L,R});
            }else{
                // [1,3] [2,5]-> [1,5]  
                // [1,6] [2,5]-> [1,6]  
                merged.get(merged.size()-1)[1] = 
                Math.max(merged.get(merged.size() -1)[1],R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

189. 轮转数组

示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] newArr = new int[n];
        for(int i=0;i<n;i++){
            newArr[ (i+k)%n ] = nums[i];
        }
        System.arraycopy(newArr,0,nums,0,n);
    }
}

238. 除了自身以外数组的乘积

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];

        int[] L = new int[n];
        int[] R = new int[n];

        L[0] = 1;
        for(int i=1;i<n;i++){
            L[i] = nums[i-1] * L[i-1];
        }

        R[n -1] = 1;
        for(int i=n-2;i>=0;i--){
            R[i] = nums[i+1] * R[i+1];
        }
        for (int i = 0; i < n; i++) {
            res[i] = L[i] * R[i];
        }
        return res;
    }
}

矩阵

73. 矩阵置零

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
  
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
  
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n= matrix[0].length;
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j] ==0){
                    row[i] = col[j] = true;
                }
            }
        }

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
        
    }
}

54. 螺旋矩阵

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<Integer>();

        if(matrix ==null || matrix.length==0 || matrix[0].length==0){
            return order;
        }

        int rows = matrix.length, columns = matrix[0].length;
        int left = 0,right = columns-1,top=0,bottom=rows-1;
        while(left<=right && top<=bottom){
            for(int i = left;i<=right;i++){
                order.add(matrix[top][i]);
            }

            for(int i=top+1;i<=bottom;i++){
                order.add(matrix[i][right]);
            }

            if(top<bottom &&left<right){

            
                for(int i = right-1;i>left;i--){
                    order.add(matrix[bottom][i]);
                }

                for(int i = bottom;i>top;i--){
                    order.add(matrix[i][left]);
                }
            }

            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }
}

48. 旋转图像

class Solution {
    public void rotate(int[][] matrix) {
        int n= matrix.length;
        for(int i=0;i<n;i++){
            // 先沿对角线反转
            for(int j=i;j<n;j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // 然后反转二维矩阵的每一行
        for(int[] row:matrix){
            reverse(row);
        }

    }
    void reverse(int[] arr){
        int i=0,j=arr.length -1;
        while(i<j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
}

240. 搜索二维矩阵 II

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m= matrix.length;
        int n=matrix[0].length;
        // 初始化在右上角
        int i=0,j=n-1;
        while(i<m&& j>=0){
            if(matrix[i][j] ==target){
                return true;
            }
            if(matrix[i][j] <target){
                // 需要大一点，往下移动
                i++;
            }else{
                // 需要小一点，往左移动
                j--;
            }
        }
        return false;
    }
}

哈希

49. 字母异位词分组

示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解释：
在 strs 中没有字符串可以通过重新排列来形成 "bat"。
字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:
输入: strs = [""]
输出: [[""]]

示例 3:
输入: strs = ["a"]
输出: [["a"]]

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map=new HashMap<String,List<String>>();
        for(String str:strs){
            char[] array= str.toCharArray();
            Arrays.sort(array);

            String key = new String(array);
            List<String> list = map.getOrDefault(key,new ArrayList<String>());
            list.add(str);
            map.put(key,list);
        }

        return new ArrayList<List<String>>(map.values());
    }
}

128. 最长连续序列

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

示例 3：
输入：nums = [1,0,1,2]
输出：3

class Solution {
    public int longestConsecutive(int[] nums) {
        // 去重
        HashSet<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }
        int longestStreak = 0;
        // 如果x-1不在哈希表中，那么说明x是连续序列的起点
        // 初始化当前序列长度为1
        // 检查x+1,x+2...是否在哈希表，更新当前连续的长度
        // 更新最长连续长度
        for(int num: num_set){
            if(!num_set.contains(num-1)){
                int currentNum = num;
                int currentLen = 1;

                while(num_set.contains(currentNum+1)){
                    currentNum+=1;
                    currentLen+=1;
                }
                longestStreak = Math.max(longestStreak,currentLen);
            }
        }

        return longestStreak;

    }
}

双指针

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量.
  
class Solution {
    public int maxArea(int[] height) {
        int l = 0, r=height.length - 1;
        int ans = 0;
        while(l<r){
            int area = Math.min(height[l],height[r])*(r-l);
            ans = Math.max(ans,area);
            if(height[l]<=height[r]){
                ++l;
            }else{
                --r;
            }
        }
        return ans;
    }
}

15. 三数之和

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

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 先排序
        Arrays.sort(nums);
        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
        for(int i=0;i<nums.length;i++){
            // 跳过重复元素
            if(i>0 && nums[i-1] == nums[i]) continue;
            int target = - nums[i];
            int l=i+1,r=nums.length-1;
            while(l<r){
                int sum = nums[l] + nums[r];
                if(sum==target){
                    res.add(Arrays.asList(nums[i],nums[l],nums[r]));

                    l++;
                    r--;
                    // 左边的当前跟前面一个比
                    while(l<r && nums[l] == nums[l-1]) l++;
                    // 右边的当前跟后面一个比
                    while(l<r && nums[r] == nums[r+1]) r--;
                }else if(sum<target){
                    l++;
                }else{
                    r--;
                }

            }
        }
        return res;
    }
}

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int sum = 0;
        
        if(n==0) return 0;
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for(int i=1;i<n;i++){
            leftMax[i] = Math.max(leftMax[i-1],height[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n-1] = height[n-1];
        for(int i=n-2;i>=0;--i){
            rightMax[i] = Math.max(rightMax[i+1],height[i]);
        }

        for(int i=0;i<n;i++){
            sum+= Math.min(leftMax[i],rightMax[i]) - height[i];
        }
        return sum;
        
    }
}

滑动窗口

3. 无重复字符的最长子串

示例 1:
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

class Solution {
    public int lengthOfLongestSubstring(String s) {

        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int res = 0;

        while(right<s.length()){
            char c = s.charAt(right);
            right++;
            // 进行窗口内数据的一系列更新
            window.put(c,window.getOrDefault(c,0)+1);
            // 判断左侧窗口是否要收缩
            while(window.get(c)>1){
                char d = s.charAt(left);
                left++;
                // 进行窗口内数据的一系列更新
                window.put(d, window.get(d) - 1);
            }
            res = Math.max(res, right - left);
        }
        return res;
    }
}

438. 找到字符串中所有字母异位词

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        Map<Character, Integer> need = new HashMap<>();
        for( char c:p.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }

        Map<Character, Integer> window = new HashMap<>();
        int left =0,right = 0,valid=0 ;
        // 合法的大小
        // 记录结果
        ArrayList<Integer> res = new ArrayList<Integer>();

        while(right<s.length()){
            char c = s.charAt(right);
            right++;
            // 进行窗口内数据的一系列更新
            if(need.containsKey(c)){
                window.put(c, window.getOrDefault(c, 0) + 1);
                if(window.get(c).equals(need.get(c))){
                    valid++;
                }
            }

            // 判断左侧窗口是否要收缩
            while(right-left >= p.length()){
                // 当窗口符合条件时，把起始索引加入res
                if(valid == need.size()){
                    res.add(left);
                }
                char d = s.charAt(left);
                left++;

                // 进行窗口内的操作
                if(need.containsKey(d)){
                    if(window.get(d).equals(need.get(d))){
                        valid--;
                    }
                    window.put(d,window.get(d)-1 );
                }
            }

        }
        return res;

    }
}

字符串

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。

示例 1：
输入：nums = [1,1,1], k = 2
输出：2

示例 2：
输入：nums = [1,2,3], k = 3
输出：2
  
class Solution {
    public int subarraySum(int[] nums, int k) {
        // 前缀和 + 哈希表优化
        int count =0,pre=0;
        // key为前缀和，value为次数
        HashMap<Integer,Integer> mp= new HashMap<>();
        mp.put(0,1);
        for(int i=0;i<nums.length;i++){
            pre += nums[i];
            // pre-k 在mp中，说明之前某个点A的累积和为pre -k
            // 由于当前的累积和为pre，就是说从那个点A到B当前点的子数之和恰好为k
            // (pre-k) [A]  + k = pre(B). A -> B 为k
            if(mp.containsKey(pre-k)){
                count+= mp.get(pre-k);
            }
            mp.put(pre,mp.getOrDefault(pre,0)+1);
        }
        return count;      
    }
}

链表

142. 环形链表 II

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(true){
            if(fast==null || fast.next ==null){
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
            // 2*(a+b) = a + 2b+ c -> a=c
            if(fast==slow) break;
        }
        //再走一个c也就是从head走向p点(入口点)，就是a
        fast = head;
        while(slow!=fast){
            slow = slow.next;
            fast=fast.next;
        }
        return fast;
    }
}

2. 两数相加

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode p1 = l1,p2=l2;
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        int carry = 0;
        while(p1!=null || p2!=null || carry!=0){
            int val = carry;
            if(p1!= null){
                val += p1.val;
                p1 = p1.next;
            }

            if(p2!=null){
                val += p2.val;
                p2 = p2.next;
            }
            carry = val / 10;
            val = val % 10;

            p.next = new ListNode(val);
            p = p.next;
        }

        return dummy.next;
    }
}

19. 删除链表的倒数第 N 个结点

class Solution {
    // 找到倒数第k个节点
    private ListNode findFromEnd(ListNode p,int k){
        ListNode p1 = p;
        for(int i = 0; i < k; i++) {
            p1 = p1.next;
        }

        ListNode p2 = p;
        while(p1!=null){
            p1 = p1.next;
            p2 = p2.next;
        }
        // p2 就是倒数第 k 个节点
        return p2;

    }
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 虚拟头节点
        ListNode dummpy = new ListNode(-1);
        dummpy.next = head;
        // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
        ListNode x = findFromEnd(dummpy,n+1);
        x.next = x.next.next;
        return dummpy.next;

    }
}

24. 两两交换链表中的节点

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 递归
        if(head==null || head.next ==null){
            return head;
        }

        ListNode newHead = head.next;
        ListNode nextHead = swapPairs(newHead.next);
        newHead.next = head;
        head.next = nextHead;
        return newHead;
    }
}

###############################################################
核心技巧：双指针（快慢、左右）、滑动窗口、前缀和、模拟法。

重点题目：移动零、盛最多水的容器、三数之和、无重复字符的最长子串、接雨水。
###############################################################

———0128————数组
53.最大子数组和 -> 动态规划 记录可能性 选A,B
56.合并区间
189.轮转数组 取模
238.除了自身以外数组的乘积 左边乘积 右边乘积

———————矩阵
73.矩阵置零 - 辅助记录
54.螺旋矩阵 -> 注意边界
48.旋转图像
240.搜索二维矩阵 II

——————–字符串

双指针

###############################################################
核心技巧：用空间换时间，快速查找。常与数组、字符串结合。

重点题目：两数之和、字母异位词分组、最长连续序列。
###############################################################

———————哈希

###############################################################
核心技巧：虚拟头节点、双指针（找环、找中点）、反转链表。

重点题目：反转链表、环形链表、合并两个有序链表、LRU缓存机制。
###############################################################

———————链表

栈
堆
二叉树

回溯
二分查找
动态规划