Hashset Applications (Duplicates · Longest Sequence · Subarray Sum)

Contains Duplicate Series

Contains Duplicate I (LeetCode 217)

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

Contains Duplicate II (LeetCode 219)

Check for identical values where the index difference is $\le k$:

boolean containsNearbyDuplicate(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>(); // key: value, value: last seen index
    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;
}

Longest Consecutive Sequence (LeetCode 128)

Find the longest sequence of consecutive integers in O(n) time (no sorting):

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

    int maxLen = 0;
    for (int n : set) {
        // Optimization: only start counting from the beginning of a sequence
        // If n-1 exists, n is not the start, so skip it.
        if (!set.contains(n - 1)) {
            int len = 1;
            while (set.contains(n + len)) {
                len++;
            }
            maxLen = Math.max(maxLen, len);
        }
    }
    return maxLen;
}

Key Optimization: By skipping nodes that aren't the start of a sequence, we ensure each element is visited at most twice, maintaining O(n) complexity.

Subarray Sum Equals K (LeetCode 560)

Prefix Sum + Hash Map: Store the frequency of prefixSum[j]. If currentSum - k exists in the map, then the subarray [j+1, i] sums to k.

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);  // Base case: prefix sum of an empty subarray is 0
    int sum = 0, count = 0;
    for (int n : nums) {
        sum += n;
        // Check if there's a previous prefix sum such that sum - prefixSum = k
        count += prefixCount.getOrDefault(sum - k, 0);
        prefixCount.merge(sum, 1, Integer::sum);
    }
    return count;
}

Contiguous Array (LeetCode 525)

Find the maximum length of a contiguous subarray with an equal number of 0s and 1s.
Trick: Treat 0 as -1. The problem transforms into finding the longest subarray with a sum of 0.

int findMaxLength(int[] nums) {
    Map<Integer, Integer> firstIndex = new HashMap<>();
    firstIndex.put(0, -1); // Initialize for prefix sum 0 at index -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;
}

4Sum II (LeetCode 454)

Count how many tuples (i, j, k, l) sum to zero, given four integer arrays:

int fourSumCount(int[] a, int[] b, int[] c, int[] d) {
    Map<Integer, Integer> map = new HashMap<>();
    // Store sums of pairs from the first two arrays
    for (int x : a) {
        for (int y : b) {
            map.merge(x + y, 1, Integer::sum);
        }
    }
    
    int count = 0;
    // For each pair in the other two arrays, check for the negative complement
    for (int x : c) {
        for (int y : d) {
            count += map.getOrDefault(-x - y, 0);
        }
    }
    return count;
}

Happy Number (LeetCode 202)

boolean isHappy(int n) {
    Set<Integer> seen = new HashSet<>();
    while (n != 1) {
        int sum = 0;
        // Sum of squares of digits
        while (n > 0) { 
            int d = n % 10; 
            sum += d * d; 
            n /= 10; 
        }
        n = sum;
        // If we revisit a sum, we are in an infinite loop
        if (!seen.add(n)) return false; 
    }
    return true;
}