← 返回学习路线

SYSTEM

哈希

八股1.5 哈希system
src/content/notes/system/哈希.md

1.5 哈希

两数之和(力扣 1)

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

最长连续序列(力扣 128)

把数放进集合,只从”序列起点”(num-1 不在集合中)开始向上数,避免重复枚举,整体 O(N)。

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) set.add(n);
        int max = 0;
        for (int n : set) {
            if (set.contains(n - 1)) continue; // 不是起点,跳过
            int cur = n, len = 1;
            while (set.contains(cur + 1)) { cur++; len++; }
            max = Math.max(max, len);
        }
        return max;
    }
}