hot1 两数之和

hot2 字母异位词分组

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

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

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

字母异位词分组（Java 实现）

思路

字母异位词的特点是：它们包含的字母种类和数量完全相同，只是字母的排列顺序不同。
因此，我们可以把每个字符串排序，排序后的结果就是这些异位词的统一标识（例如 "eat"、"tea"、"ate" 排序后都变成 "aet"）。
利用这个统一标识作为哈希表的键，将所有具有相同键的字符串收集到同一个列表中，最后返回哈希表中所有值即可。

代码（排序 + 哈希表）

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 哈希表：键为排序后的字符串，值为该组异位词的列表
        Map<String, List<String>> map = new HashMap<>();

        for (String s : strs) {
            // 将字符串转为字符数组，排序后得到标准键
            char[] charArray = s.toCharArray();
            Arrays.sort(charArray);
            String key = new String(charArray);

            // 获取键对应的列表，若不存在则新建一个列表
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(s);               // 将原字符串加入列表
            map.put(key, list);        // 更新哈希表
        }

        // 返回所有分组（哈希表的值集合）
        return new ArrayList<>(map.values());
    }
}

详细注释说明

Map<String, List<String>> map = new HashMap<>();
创建一个哈希表，用于存储“排序后的字符串 → 异位词组列表”的映射。
char[] charArray = s.toCharArray();
将当前字符串 s 转换成字符数组，便于排序。
Arrays.sort(charArray);
对字符数组进行排序，这样所有字母异位词都会得到相同的字符序列。
String key = new String(charArray);
将排序后的字符数组重新构造成字符串，作为该组异位词的唯一键。
List<String> list = map.getOrDefault(key, new ArrayList<>());
从哈希表中获取该键对应的列表。如果键不存在，则返回一个新创建的 ArrayList，避免空指针。
list.add(s);
将原始字符串 s 添加到对应的异位词组中。
map.put(key, list);
将更新后的列表放回哈希表（因为 getOrDefault 返回的新列表可能尚未存入 map，需要显式 put 确保关联）。
return new ArrayList<>(map.values());
哈希表的 values() 方法返回所有分组列表的集合，将其转换为 ArrayList 作为最终结果。

复杂度分析

时间复杂度：O(n * k log k)
其中 n 是字符串数组长度，k 是字符串的最大长度。每个字符串排序需要 O(k log k)，遍历所有字符串共 n 次。
空间复杂度：O(n * k)
需要存储所有字符串及其对应的键，哈希表总存储量与输入规模成正比。

hot3 最长连续序列

题目描述

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

1
2
3

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

示例 2：

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

示例 3：

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

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109

完整代码

class Solution {
    public int longestConsecutive(int[] nums) {
        // 边界情况：空数组返回0
        if (nums.length == 0) return 0;
        // 边界情况：只有一个元素，最长连续就是1
        if (nums.length == 1) return 1;
        
        // 第一步：排序
        Arrays.sort(nums);
        
        int result = 1;        // 记录最长连续序列的长度，初始为1
        int point = 0;         // 当前连续序列的起点索引
        int length = 1;        // 当前连续序列的长度
        
        // 第二步：遍历数组，比较相邻元素
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i + 1] == nums[i]) {
                // 情况1：元素重复，跳过，起点不变
                continue;
            } else if (nums[i + 1] - nums[i] == 1) {
                // 情况2：连续，计算从 point 到 i+1 的长度
                length = (i + 1) - point + 1;
                // 更新最长长度
                result = Math.max(result, length);
            } else {
                // 情况3：不连续，新起点为 i+1
                point = i + 1;
                length = 1;  // 重置当前长度为1
            }
        }
        
        // 返回最长连续序列的长度
        return result;
    }
}

逐行讲解

1	if (nums.length == 0) return 0;

如果数组为空，没有连续序列，返回 0

1	if (nums.length == 1) return 1;

如果只有一个元素，它自己就是长度为 1 的连续序列

1	Arrays.sort(nums);

将数组从小到大排序
例如：[3, 1, 2, 4] → [1, 2, 3, 4]

1
2
3

int result = 1;    // 最长连续序列长度
int point = 0;     // 当前连续序列的起点索引
int length = 1;    // 当前连续序列的长度

result：记录全局最长连续序列的长度
point：标记当前连续序列从哪个索引开始
length：记录当前连续序列的长度

1	for (int i = 0; i < nums.length - 1; i++) {

遍历数组，比较 nums[i] 和 nums[i+1]
注意是 i < nums.length - 1，因为要访问 i+1

1
2
3

if (nums[i + 1] == nums[i]) {
    continue;
}

情况1：重复元素
例如：[1, 1, 2]，当 i=0 时，nums[1] == nums[0]，跳过
重复元素不影响连续性，直接继续下一次循环

else if (nums[i + 1] - nums[i] == 1) {
    length = (i + 1) - point + 1;
    result = Math.max(result, length);
}

情况2：连续
例如：[1, 2, 3]
- i=0：2-1=1，连续，length = 1-0+1 = 2，result = max(1,2) = 2
- i=1：3-2=1，连续，length = 2-0+1 = 3，result = max(2,3) = 3

else {
    point = i + 1;
    length = 1;
}

情况3：不连续
例如：[1, 2, 5, 6]
- i=1：5-2=3，不连续
- 新的连续序列从索引 2（即数字 5）开始
- point = 1+1 = 2
- length = 1，重置长度

1	return result;

返回记录的最长连续序列长度

举例演示

输入：nums = [1, 2, 4, 5, 6]

排序后：[1, 2, 4, 5, 6]

i	nums[i]	nums[i+1]	差值	操作	point	length	result
初始	-	-	-	-	0	1	1
0	1	2	1	连续	0	2	2
1	2	4	2	不连续	2	1	2
2	4	5	1	连续	2	2	2
3	5	6	1	连续	2	3	3

返回 result = 3 ✅

复杂度分析

时间复杂度：O(n log n)
- 排序需要 O(n log n)
- 遍历一次数组需要 O(n)
- 总体为 O(n log n)
空间复杂度：O(1)
- 只用了几个变量，没有额外空间

Hot4 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

1 2	输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]

示例 2:

1 2	输入: nums = [0] 输出: [0]

提示:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

解法

思路
双指针：fast 找非零，slow 接收。搬完后 slow 之后全填 0。

代码

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow++] = nums[fast];  // 非零搬到 slow 位置
            }
        }
        for (int i = slow; i < nums.length; i++) {
            nums[i] = 0;                    // 剩下的补 0
        }
    }
}
复杂度：时间 O(n)，空间 O(1)。

盛最多水的容器

思路

双指针从两端往中间夹。面积 = min(左高, 右高) × 宽度。每次移动较短的那一边，因为移动长边面积只会变小。

代码

java

class Solution {
    public int maxArea(int[] height) {
        int left = 0, 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;
    }
}

复杂度：时间 O(n)，空间 O(1)。

三数之和

思路

先排序。固定第一个数 nums[i]，剩下两个用左右双指针找。三处去重：固定数去重、左指针去重、右指针去重。

代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break;                              // 第一个数 >0，后面不可能凑 0
            if (i > 0 && nums[i] == nums[i - 1]) continue;       // 固定数去重

            int left = i + 1, right = nums.length - 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++;   // 和太小，左指针右移
                else right--;                 // 和太大，右指针左移
            }
        }
        return result;
    }
}

复杂度：时间 O(n²)，空间 O(1)（不计结果）。

力扣算法题目笔记

hot1 两数之和

hot2 字母异位词分组

字母异位词分组（Java 实现）

思路

代码（排序 + 哈希表）

详细注释说明

复杂度分析

hot3 最长连续序列

题目描述

完整代码

逐行讲解

举例演示

复杂度分析

Hot4 移动零

解法

盛最多水的容器

思路

代码

三数之和

思路

代码