package advanced.scan.window.lc219_containsduplicate2;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array
 * such that nums[i] = nums[j] and the difference between i and j is at most k.
 */
public class Solution {

    // My 2nd: much easier and elegant using Sliding Window.
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums.length == 0 || k <= 0) {
            return false;
        }

        Set<Integer> numSet = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!numSet.add(nums[i])) {
                return true;
            }

            /* How many element in Set now? K */
            if (i >= k) {
                numSet.remove(nums[i - k]);
            }

            /* At most K-1 here */
        }
        return false;
    }

    // My 1st
    public boolean containsNearbyDuplicate1(int[] nums, int k) {
        Map<Integer,Integer> exist = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (exist.containsKey(nums[i])
                    && (i - exist.get(nums[i]) <= k)) {
                return true;
            }
            exist.put(nums[i], i);
        }
        return false;
    }

}

@@ -376,16 +376,370 @@
 tion %7B%0A%0A
+    public boolean containsNearbyDuplicate(int%5B%5D nums, int k) %7B%0A        Set%3CInteger%3E seen = new HashSet%3C%3E(); /* dist=k =%3E k+1 nums =%3E save nearby k numbers */%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            if (!seen.add(nums%5Bi%5D)) return true;%0A            if (seen.size() %3E k) seen.remove(nums%5Bi - k%5D);%0A        %7D%0A        return false;%0A    %7D%0A%0A
     // M
@@ -825,32 +825,33 @@
 sNearbyDuplicate
+2
 (int%5B%5D nums, int
@@ -1240,32 +1240,32 @@
 %0A            %7D%0A%0A
-
             /* A
@@ -1279,16 +1279,67 @@
 K-1 here
+? Wrong! i=k, numSet has k+1 elts, so now we have k
  */%0A    

contains duplicate II