leetcode hot 100

发表于 更新于 分类于

哈希

两数之和

题意： 在数组中找到两个数，使它们的和等于 target，并返回它们的索引。

解题思路：

  • 创建一个 HashMap 存储已遍历过的数字及其下标；
  • 对于当前数字 nums[i]，计算 target - nums[i]；
  • 如果这个差值在哈希表中存在，说明之前的某个数与当前数之和等于 target；
  • 立即返回两个下标。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.HashMap;
import java.util.Map;

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[0];
}

复杂度：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

字母异位词分组

题意：

给你一个字符串数组 strs，请你将 字母异位词 组合在一起。 字母异位词 是指两个字符串中的字母相同，但排列顺序不同。 返回所有字母异位词的分组（顺序不限）。

示例：

输入：

1
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出：

1
[["bat"], ["nat","tan"], ["ate","eat","tea"]]

解题思路：

核心思想：

  • 异位词排序后是相同的字符串。
  • 因此，可以用一个哈希表（HashMap）来将“排序后的字符串”作为 key，把相同 key 的字符串加入同一个列表中。

步骤：

  1. 创建一个 HashMap<String, List<String>>。
  2. 遍历 strs 中的每个字符串：
    • 将其字符排序，得到 key；
    • 将原字符串放入该 key 对应的列表中。
  3. 最后返回哈希表中所有的 value 列表。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

复杂度分析：

  • 时间复杂度：O(n * k log k) 其中 n 是字符串个数，k 是每个字符串的最大长度（排序复杂度为 k log k）。
  • 空间复杂度：O(n * k) 存储所有字符串以及中间哈希表结构。