LeetCode 热题 100

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;
}