LeetCode 热题 100 | 哈希
哈希基础
- 当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希。
- 为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作。
- 一般哈希碰撞有两种解决方法， 拉链法和线性探测法。
拉链法：发生冲突的元素都被存储在链表中。
线性探测法：使用线性探测法，一定要保证tableSize大于dataSize。冲突的位置，放了A，那么就向下找一个空位放置B。- 常见的三种哈希结构：
数组：哈希的值比较小，范围也比较小，范围可控。空间有限。
set(集合)：哈希的值很大。空间无限，但是没法保存多余的信息。
map(映射)：k-v结构。空间无限，但是很占内存，效率比前两个都低。
1. 两数之和
题目讲解：LeetCode
重点：
- 用map哈希方便快速查找是否有diff值及diff的索引
思路：
- 从头遍历nums数组，一边遍历一边保存数值和索引进map，后面如果遇到差值刚好为前面的数值，则找到结果。
复杂度：
- N 是元素数量。
- 时间复杂度：O(N)。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。
- 空间复杂度：O(N)。主要为哈希表的开销。
public int[] twoSum(int[] nums, int target) {// 重点: 用map保存元素索引HashMap<Integer, Integer> numsMap = new HashMap<>();int[] result = new int[2];for (int i = 0; i < nums.length; i++) {int cur = nums[i];int diff = target - cur;if (numsMap.containsKey(diff)) {result[0] = numsMap.get(diff);result[1] = i;return result;} else {numsMap.put(cur, i);}}return result;
}
49. 字母异位词分组
题目讲解：LeetCode
重点：
- 用sort好的String当map的key。
思路：
- 遍历strs数组，把每个字符串toCharArray后sort转成String，检查map中是否有相同的String键，如果有加入List，没有则创建List。
复杂度：
- n 是字符串的数量，k 是字符串的的最大长度。
- 时间复杂度：需要遍历 n 个字符串，对于每个字符串，需要 O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表，因此总时间复杂度是 O(nklogk)。
- 空间复杂度：O(nk)。需要用哈希表存储全部字符串。
public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> hashStrMap = new HashMap<>();for (String str : strs) {// 重点: 字母异位词sort之后肯定一致char[] charArray = str.toCharArray();Arrays.sort(charArray);String key = new String(charArray);List<String> value = hashStrMap.getOrDefault(key, new ArrayList<>());value.add(str);hashStrMap.put(key, value);}return new ArrayList<>(hashStrMap.values());
}
128. 最长连续序列
题目讲解：LeetCode
重点：
- 每个数都判断一次这个数是不是连续序列的开头那个数。
思路：
- 把nums数组存入Set中自动去重
- 遍历Set，判断当前元素是否是连续序列的开头元素，也就是判断Set中是否存在num - 1。如果存在，直接continue。如果不存在，说明是连续序列的开头。不断检测num + 1是否存在于Set中就能计算出该连续元素的长度。最后取最长的长度即可。
复杂度：
- n 为数组的长度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
public int longestConsecutive(int[] nums) {Set<Integer> numsSet = new HashSet<>();for (int num : nums) {numsSet.add(num);}int result = 0;for (int num : numsSet) {// 重点: 判断是否是连续序列的开头元素if (numsSet.contains(num - 1)) {continue;}int cur = num;int curResult = 0;while (numsSet.contains(cur)) {curResult++;cur++;}result = Math.max(curResult, result);}return result;
}