哈希集合应用（查重 · 最长序列 · 子数组和）

存在重复元素系列

存在重复元素 I（LeetCode 217）

boolean containsDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int n : nums) if (!seen.add(n)) return true;
    return false;
}

存在重复元素 II（LeetCode 219）

同值且下标差 ≤ k：

boolean containsNearbyDuplicate(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) return true;
        map.put(nums[i], i);
    }
    return false;
}

最长连续序列（LeetCode 128）

要求 O(n)，不用排序：

int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) set.add(n);

    int maxLen = 0;
    for (int n : set) {
        // 只从序列起点开始计数（n-1 不存在，说明 n 是起点）
        if (!set.contains(n - 1)) {
            int len = 1;
            while (set.contains(n + len)) len++;
            maxLen = Math.max(maxLen, len);
        }
    }
    return maxLen;
}

关键：跳过非起点，避免重复计算，整体只遍历一次每个元素。

和为 K 的子数组（LeetCode 560）

前缀和 + 哈希：cunter 中存 prefix[j] = k 的次数，若 prefix[i] - k 在 map 中，则子数组 [j+1, i] 的和为 k。

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);  // 空前缀
    int sum = 0, count = 0;
    for (int n : nums) {
        sum += n;
        count += prefixCount.getOrDefault(sum - k, 0);
        prefixCount.merge(sum, 1, Integer::sum);
    }
    return count;
}

连续数组（LeetCode 525）

含等量 0 和 1 的最长连续子数组：将 0 替换为 -1，转化为前缀和为 0 的最长子数组。

int findMaxLength(int[] nums) {
    Map<Integer, Integer> firstIndex = new HashMap<>();
    firstIndex.put(0, -1);
    int sum = 0, maxLen = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += (nums[i] == 0) ? -1 : 1;
        if (firstIndex.containsKey(sum))
            maxLen = Math.max(maxLen, i - firstIndex.get(sum));
        else
            firstIndex.put(sum, i);
    }
    return maxLen;
}

四数之和 II（LeetCode 454）

四个数组各取一个数，和为 0 的方案数：

int fourSumCount(int[] a, int[] b, int[] c, int[] d) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int x : a) for (int y : b) map.merge(x + y, 1, Integer::sum);
    int count = 0;
    for (int x : c) for (int y : d) count += map.getOrDefault(-x - y, 0);
    return count;
}

快乐数（LeetCode 202）

boolean isHappy(int n) {
    Set<Integer> seen = new HashSet<>();
    while (n != 1) {
        int sum = 0;
        while (n > 0) { int d = n % 10; sum += d * d; n /= 10; }
        n = sum;
        if (!seen.add(n)) return false;  // 进入循环
    }
    return true;
}