彭阳门户网站建设_什么是电子商务网站推广_百度竞价排名平台_域名停靠网页推广大全2023

哈希基础

• 当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希。
• 为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作。
• 一般哈希碰撞有两种解决方法， 拉链法和线性探测法。
  拉链法：发生冲突的元素都被存储在链表中。
  线性探测法：使用线性探测法，一定要保证tableSize大于dataSize。冲突的位置，放了A，那么就向下找一个空位放置B。
• 常见的三种哈希结构：
  数组：哈希的值比较小，范围也比较小，范围可控。空间有限。
  set(集合)：哈希的值很大。空间无限，但是没法保存多余的信息。
  map(映射)：k-v结构。空间无限，但是很占内存，效率比前两个都低。

1. 两数之和

题目讲解：LeetCode
重点：

1. 用map哈希方便快速查找是否有diff值及diff的索引

思路：

1. 从头遍历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
重点：

1. 用sort好的String当map的key。

思路：

1. 遍历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
重点：

1. 每个数都判断一次这个数是不是连续序列的开头那个数。

思路：

1. 把nums数组存入Set中自动去重
2. 遍历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;
}