LeetCode 532. K-diff number pairs in array

532. Array k-diff Number pair

【 Hashtable 】 Compare the dishes made by yourself , First put all the points into the hash table , Then enumerate each element , Find out whether the larger element is in the hash table .k=0 This situation needs to be considered separately .

class Solution {
    public int findPairs(int[] nums, int k) {
        int ans = 0;
        if(k == 0){
            Map<Integer, Integer> map = new HashMap();
            for(var x: nums){
                map.put(x, map.getOrDefault(x, 0) + 1);
            }
            for(var key: map.keySet()){
                if(map.get(key) > 1) ans++;
            }
            return ans;
        }
        Set<Integer> set = new HashSet(){
   {
            for(var x: nums) add(x);
        }};
        for(var x: set){
            if(set.contains(x + k)){
                ans++;
            }
        }
        return ans;
    }
}

【 Improved hash table 】 because k Is constant , So for any tuple , We only need to save a smaller value , The specific method is ：

1. Open two hash tables , An element used to store enumerated elements

2. The other is used to store smaller values that meet the conditions

class Solution {
    // 2:40 hash
    public int findPairs(int[] nums, int k) {
        Set<Integer> visit = new HashSet();
        Set<Integer> ans = new HashSet();
        for(var x: nums){
            if(visit.contains(x - k)){
                ans.add(x - k);
            }
            if(visit.contains(x + k)){
                ans.add(x);
            }
            visit.add(x);
        }
        return ans.size();
    }
}

【 Sort + Two points 】 Sort the array first , Then for each element , Find out whether it is larger than this element starting from the next coordinate k Value . It should be noted that the calculated elements should be skipped , Because it's in order , Repeating elements are all together , So judge whether it is the same as the previous element .

class Solution {

    //  Sort + Two points  2:50 7

    public int binarySearch(int[] nums, int target, int left){
        int right = nums.length - 1;
        while(left <= right){
            int mid = (left + right) >>> 1;
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }

    public int findPairs(int[] nums, int k) {
        Arrays.sort(nums);
        int ans = 0;
        for(var i = 0; i < nums.length; i++){
            if(i != 0 && nums[i] == nums[i - 1]) continue;
            if(binarySearch(nums, nums[i] + k, i + 1) != -1) ans++;
        }
        return ans;
    }
}

【 Sort + Double pointer 】 We found the sorted array , Some element nums[i] And elements bigger than him nums[j],j With i Moving backwards . In this way, it has the characteristics of double pointers .

class Solution {

    //  Sort + Double pointer  3:07

    public int findPairs(int[] nums, int k) {
        Arrays.sort(nums);
        int ans = 0, j = 1;
        for(var i = 0; i < nums.length; i++){
            if(i != 0 && nums[i] == nums[i - 1]) continue;
            while(j < nums.length && nums[j] <= nums[i] + k) j++;
            if(j - 1 != i && nums[j - 1] == nums[i] + k) ans++;
        }
        return ans;
    }
}