LeetCode

LeetCode Java解法 每日更新

我会在这里每日更新 LeetCode 的解题思路以及源码，欢迎大家提 issue (不喜勿喷)(虽然也没人看)

📚 目录

哈希表

Problem 1 - 两数之和

作为 LeetCode Problem 1，无数人从这一题入门，还是很有纪念意义的。

25年4月的时候，对未来一片迷茫的我，决定收起以前的散漫，开始系统性学习编程，学了一部分Java SE之后，偶然了解到LeetCode，故事从此开始…

25年5月第一次做的时候，用的是硬破解（如下），虽然时间复杂度很高也很低效，但是觉得还是挺有意思的，做出来很有成就感，可惜第二题就做不出来了，也看不懂题目…

当时的代码

public int[] twoSum(int[] nums, int target) {
    int[] result = new int[2]; // 返回数组，用来存下标的

    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = i + 1; j < nums.length; j++) { //直接来一手双层循环 也是时间复杂度高的关键
            if (nums[i] + nums[j] == target) {
                result[0] = i;
                result[1] = j;
            }
        }
    }
    return result;
}

25年10月，学成 Java Web 归来并且做过单体项目但是投简历仍然石沉大海的我，决定刷刷算法充实一下自己…

于是打开了 LeetCode，开始每天都做几题，做了七八题之后，决定开始写这篇笔记来记录一下所思所想。

题目描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

题解：

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> numMap = new HashMap<>(); // 哈希表
    for (int i = 0; i < nums.length; i++) { // 遍历数组（只需最多一轮）
        if (numMap.containsKey(target - nums[i])) { // 若存在另一位数字
            return new int[]{numMap.get(target - nums[i]), i}; // 构建数组并返回结果
        }
        numMap.put(nums[i], i); // 若不存在，则将当前数字和下标存入哈希表，以便下次查找
    }
    return null;
}

解题思路：

💡 为什么这样做？

这样做的好处是对于数组 nums，我们只需要遍历一次，遍历过程中查找 target - nums[i] 的时候，由于使用哈希表，查找时间复杂度是 O(1)，也是典型的空间换时间策略。

📌 哈希表的优势： 哈希表非常适合快速查找，因为哈希表的原理是将值转换成哈希值来构建索引，这样下次查找该值的时候相当于直接使用索引，所以时间复杂度接近 O(1)。

复杂度分析：

核心技巧： 用空间换时间，将查找时间从 O(n) 降到 O(1)

Problem 49 - 字母异位词分组

题目描述：
给定一个字符串数组，请你将字母异位词组合在一起。字母异位词是由重新排列源单词的所有字母得到的一个新单词。

示例：

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

解释：
- "bat" 无法通过重新排列形成其他单词
- "nat" 和 "tan" 是字母异位词
- "ate"、"eat" 和 "tea" 是字母异位词

题解：

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>(); // 依然是哈希表
    for (String str : strs) { // 遍历数组
        char[] chars = str.toCharArray(); // 将遍历到的字符串转换为字符数组
        Arrays.sort(chars); // 对字符数组进行排序
        String key = new String(chars); // 将排序后的字符数组转换为字符串作为 key
        map.putIfAbsent(key, new ArrayList<>()); // 如果 key 不存在，则创建一个空的 ArrayList
        map.get(key).add(str); // 将当前字符串添加到对应的 key 的 ArrayList 中
    }
    return map.values().stream().toList(); // 将 map 的值转换为 List返回
}

解题思路：

💡 核心思想：

为什么选择哈希表？因为哈希表的 Key-Value 结构非常适合这道题的分组需求！

📌 关于字符排序： Unicode 字符集的每个字符都有唯一的编码，因此我们可以将字符串中的字符进行排序。所有异位词排序后会得到相同的字符串，比如 “eat”、”tea”、”ate” 排序后都是 “aet”，这样就可以作为同一个 key 进行分组。

将排序过后的字符转换成字符串作为key的时候，我们需要将原字符串存入一个数组，也就是该key的value，以方便后续返回。

虽然需要对每个字符串进行排序，但整体效率仍然很高，时间复杂度为 O(n × k log k)

本题应该是还有其他更高效的解法的，但是我这种解法效率也还行，代码比较简洁易懂

复杂度分析：

核心技巧： 寻找异位词的统一特征（排序后相同）作为哈希的 key

Problem 128 - 最长连续序列

题目描述：
给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。要求时间复杂度为 O(n)。

示例 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

解题思路（方法一 排序）： （不推荐）

题解：

public int longestConsecutive(int[] nums) {
    if (nums.length == 0 || nums.length == 1) return nums.length; // 判断数组长度，0 或 1 直接返回
    Arrays.sort(nums); // 排序，让无序变成有序，这样数字就连续了...
    Set<Integer> numSet = new LinkedHashSet<>(); // 使用 LinkedHashSet 保持顺序和高效查询以及去重
    Arrays.stream(nums).forEach(numSet::add); // 将数组元素添加到 Set 中
    int count = 1; // 用于记录当前连续序列的长度
    int max = 1; // 用于记录最长连续序列的长度
    for (int num : numSet) {
        if (numSet.contains(num + 1)) count++; // 如果存在下一个数字，则长度加 1
        else {
            max = Math.max(max, count); // 如果中断，更新最长连续序列长度
            if (numSet.size() - max <= max) break; // 如果剩余元素不足以超过当前最大值，提前结束
            count = 1; // 重置当前长度
        }
    }
    return max;
}

复杂度分析：

好吧，这是我第一次做的时候的所使用的方法，用了这么一种有效但是很低效的方法，低效是因为在循环的时候遍历的整个数组，对每位数字都去计算由他开头的连续数字长度

看了一下题解，不得不佩服天才的脑洞是真的大…把时间复杂度优化到极致，也就是以下做法 ↓

解题思路（方法二 哈希优化）： ⭐ 推荐

题解：

public int longestConsecutive(int[] nums) {
    Set<Integer> numSet = new HashSet<>(); // 使用 HashSet 存储所有数字
    Arrays.stream(nums).forEach(numSet::add); // 将数组元素添加到 Set 中
    int count = 1; // 用于记录当前连续序列的长度
    int max = 0; // 用于记录最长连续序列的长度
    for (int num : numSet) {
        if (numSet.contains(num - 1)) continue;
        // 上一句的意思是，找到连续数字的起点，如果不存在上一个数则代表该数是起点，才执行下面的代码，反之则跳过
        while (numSet.contains(num + 1)) { // 匹配下一个数字
            count++; // 统计长度
            num++; // 更新数字，下一轮匹配下下...个数字，一直循环，直到不满足循环条件退出
        }
        max = Math.max(count, max); // 当执行到这里，代表该数字是连续数字的终点，更新最长连续序列长度
        count = 1; // 重置当前长度，继续匹配下一个数字
        if (numSet.size() - max <= max) break; // 如果剩余元素不足以超过当前最大值，提前结束
    }
    return max;
}

复杂度分析：

核心技巧： 使用哈希集合快速判断元素存在性，找到序列起点避免重复计算

不得不说，想出这种解法的人是真的天才才才才才！！！看到这种解法我有种豁然开朗的感觉，还是想说NB！

这种解法的关键在于，通过 num-1 来检测当前遍历到的数字是不是连续数字的起点，如果不是就不要浪费时间，直接下一个！

当遍历到的数字在集合里找不到 num-1，则说明当前数字是连续数字的起点，才开始统计长度

我在最后还是加上了截断优化，如果剩余元素不足以超过当前最大值，提前结束，避免无用功

另外想说的是，所有与优化查询时间有关的，都可以用哈希表，时间复杂度为 O(1)，发明哈希表的也是个天才！

双指针

Problem 11 - 盛最多水的容器

题目描述：
给定一个长度为 n 的整数数组 height，有 n 条垂线，找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

题解：

public int maxArea(int[] height) {
    int left = 0; // 左指针
    int right = height.length - 1; // 右指针
    int max = 0; // 用于记录最大面积
    while (left < right) { // 循环条件，左指针小于右指针，如果两指针已经相邻，代表所有线段都遍历过了，退出循环
        int area = Math.min(height[left], height[right]) * (right - left); // 计算当前容器的面积
        max = Math.max(max, area); // 更新最大面积
        if (height[left] < height[right]) { // 如果左边的线段更短，则移动左指针，否则移动右指针
            left++;
        } else {
            right--;
        }
    }
    return max;
}

解题思路：

木桶效应大家应该听过，本题也一样，水的高度取决于较短的那一边，那么如何保证找到面积最大的可能呢？

其实，我们并没办法直接找出最优解，只能通过尝试所有组合来选出最大值。

那么问题就变成了：如何用效率最高的方式找到最大的值？

我这里使用的是双指针，通过双指针来维护容器的左右两边。如果要找出最大值，那么我们应该通过移动某一条边的方式来找到让容器面积更大的可能。那么问题是，如果一侧的边更长，一侧的边更短，我们应该移动哪一条？

答案是：移动较短的那一侧，因为移动较长的那一侧不可能增加面积。

为什么呢？大家想想，哪怕移动长的那一侧之后，那一侧变得很长很长，由于木桶效应，实际上的面积还是会受到短的一侧控制。

也就是说，实际上的面积是(right - left) * min_height，所以我们移动长的边，只会缩小面积！

所以，每次移动较短的边，哪怕移动后底更短，可能导致面积更小，我们依然要博取一线生机！去不断的赌高度变得更高，用一次次可能提升的高度来试图在底越来越小的情况下找到更大面积，直到找完所有组合，选出最大值并返回。

这是典型的贪心算法，每次选择一个局部最优解，然后去尝试去扩展这个局部最优解，直到找到全局最优解。

人生也是一样…没人知道明天会发生什么，我们总是选择从当下来看的最优解，哪怕是所谓布局五年十年所谓职业规划，依然是站在当前这个时间点，去选择一个最优解，或者说符合自己认知的最优解，然后随着一步步成长，不断地去尝试扩展这个最优解…

唯一不一样的是，人生没有最大值，也没有机会给你选最大值。

复杂度分析：

核心技巧： 贪心思想 + 双指针，每次移动较短边才可能找到更大面积

Problem 15 - 三数之和

题目描述：
给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。

题解：

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;
    Arrays.sort(nums); // 先排序
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复元素
        int left = i + 1; // 左指针
        int right = n - 1; // 右指针
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.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 < 0) left++; // 如果和小于 0，则 left 向右移动
            else right--; // 如果和大于 0，则 right 向左移动

        }
    }
    return result;
}

解题思路：

  1. 先对数组进行排序
  2. 固定一个数 nums[i]，然后使用双指针在剩余数组中寻找两个数，使得三数之和为 0
  3. 通过跳过重复元素来去重，避免重复的三元组

这种做法是基于排序和双指针的，为什么需要排序而不用哈希表呢？因为如果用哈希表，就没办法同时找到三个数的和为0，而且本题的数字是可以重复的。所以我们必须要通过三个指针来实现，也就是一个固定指针和两个动态指针，并且要做到三个指针永不碰撞，也就是题目里的满足 i != j、i != k 且 j != k。

关于为什么要排序？刚才讲我们需要用到双指针，那么如果不排序，双指针从边界开始的话，就没办法保证每次移动指针都是最高效的做法，甚至压根不明白指针往哪里移动，最后只能遍历多次，会导致很多次无效操作。

由于本题数字范围有负数，那么我们排序完之后，就变成了类似数轴的形式，如下：

示例：nums = [-1, 0, 1, 2, -1, -4]

排序前：[-1, 0, 1, 2, -1, -4]

排序后：[-4, -1, -1, 0, 1, 2]

数轴表示：
-4   -1    -1     0     1     2
├─────┼─────┼─────┼─────┼─────┤
i    i+1                     n-1

我们将固定指针设为 nums[i]，左指针初始值设为 i+1，右指针初始值设为 n-1，每次遍历我们移动固定指针，那么问题就简化成了：通过移动左右指针来使 left + right = 0 - nums[i]。

那怎么知道移动左指针还是右指针呢？诶！我们刚才的排序就起到作用了 ↓

排序后，我们就可以根据 sum 的正负来判断应该移动哪个指针：

可是…这样就结束了吗？我们是不是忽略了什么…？比如…如果遍历到的数字和上一次遍历到的重复了？又或者在移动双指针寻找匹配值的时候，发现有重复的数字的时候，会导致结果也重复一次，而题目却要求对结果进行去重，如果最后再单独处理的话，是不是有些麻烦了？

所以我们应该在遍历的过程中，对三个指针都进行去重处理！ 怎么做呢？

看到这里可能有同学会觉得疑惑，既然这么麻烦为什么不一开始就把数组去重呢？

注意区分两个概念：

如果一开始就对数组去重，比如 [-1,-1,2] 变成 [-1,2]，那我们就永远找不到 [-1,-1,2] 这个答案了！

那么问题来了：我们明明对数字进行了跳过处理，会不会把 [-1,-1,2] 这种答案也跳过了？

这里就不得不提三指针的巧妙之处了！关键在于去重的时机：

` if (i > 0 && nums[i] == nums[i - 1]) continue; `

我们是处理完当前重复数字之后，检测到下一个还是重复的才跳过。举个例子：

数组：[-1, -1, 2]
       ↑
      i=0，第一次遇到 -1，正常处理，可以找到 [-1,-1,2]

            ↑
           i=1，第二次遇到 -1，发现和前一个一样，跳过！最后结果只有一个！
           没有重复！由于 left = i + 1，所以也不会对前面固定指针已经遍历过的数字重复计算

如果反过来，写成 if (i < n-1 && nums[i] == nums[i + 1]) continue;（检测到和后面一样就跳过），那就会出问题：

数组：[-1, -1, 2]
       ↑
      i=0，发现和后面一样，跳过了！

            ↑
           i=1，最后一个 -1 才处理，但 left = i+1 = 2，已经越界了！
           就算没有越界，也会导致遗漏结果！

所以，先处理再跳过的做法保证了每组重复数字的双指针会正确处理重复元素，从而不会遗漏包含重复元素的结果！

复杂度分析：

核心技巧： 排序 + 双指针，将三数之和转化为两数之和问题

Problem 42 - 接雨水

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

解题思路（方法一 按层统计）： 查看代码

复杂度分析：

其实这种暴力破解按理来讲可以…可惜的是没有通过最后的几个测试用例，超时了，所以有以下更高效的方法！（如下 ↓）

解题思路（方法二 双指针优化）： ⭐ 推荐

题解：

public int trap(int[] height) {
    int left = 0; // 左指针
    int right = height.length - 1; // 右指针
    int leftMax = 0; // 左边最大值
    int rightMax = 0; // 右边最大值
    int result = 0; // 结果
    while (left < right) { // 当左指针小于右指针时
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left]; // 如果左指针的高度大于左边最大值，则更新左边最大值
            } else {
                result += leftMax - height[left]; // 否则累加雨水
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right]; // 如果右指针的高度大于右边最大值，则更新右边最大值
            } else {
                result += rightMax - height[right]; // 否则累加雨水
            }
            right--;
        }
    }
    return result;
}

复杂度分析：

核心技巧： 双指针 + 贪心，利用”木桶效应”原理，较矮侧决定水位

Problem 283 - 移动零

题目描述：
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。必须在不复制数组的情况下原地对数组进行操作。

题解：

public void moveZeroes(int[] nums) {
    int n = nums.length;
    if (n != 0 && n != 1) {
        int index = 0; // 慢指针，记录非零元素应该放置的位置
        for (int i = 0; i < n; i++) { // 快指针遍历数组
            if (nums[i] != 0) {
                nums[index++] = nums[i]; // 先赋值，再 index++
            }
        }
        while (index < n) { // 将剩余位置填充为 0
            nums[index++] = 0;
        }
    }
}

解题思路：

复杂度分析：

核心技巧： 快慢指针，慢指针维护”已处理区域”的边界

滑动窗口

Problem 3 - 无重复字符的最长子串

题目描述：
给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。

解题思路（方法一 - 基础滑动窗口）： 查看代码

复杂度分析：

解题思路（方法二 - 优化滑动窗口）： ⭐ 推荐

题解：

public int lengthOfLongestSubstring(String s) {
    if (s.isEmpty() || s.length() == 1) return s.length();
    int left = 0; // 左指针
    int right = 0; // 右指针
    int max = 0; // 最大长度
    Map<Character, Integer> map = new HashMap<>(); // 记录字符最后出现的位置
    // "abcabcbb"："a" → "ab" → "abc" → "bca" → "cab" → "abc" → "cb" → "b"，最大长度为 3
    while (right < s.length()) {
        char c = s.charAt(right); // 获取当前字符
        if (map.containsKey(c) && map.get(c) >= left) {
            left = map.get(c) + 1; // 将左指针移动到重复字符上次出现位置的下一位
        }
        max = Math.max(max, right - left + 1); // 更新最大长度
        map.put(c, right); // 记录字符位置
        right++; // 右指针右移
    }
    return max;
}

复杂度分析：

核心技巧：

🏷️ 算法分类总览

算法类型 题目编号 题目数量
哈希表 1, 49, 128 3 题
双指针 11, 15, 42, 283 4 题
滑动窗口 3 1 题

💡 算法技巧总结

哈希表使用场景

双指针使用场景

滑动窗口使用场景

Made with ❤️ by ZH0531