🌕 🌕 532. 数组中的 k-diff 数对

难度: 🌕 🌕

问题描述

---

解法 1 - 排序 + 双指针

class Solution {
    public int findPairs(int[] nums, int k) {
        // 思路：
        // 排序
        // 双指针法，固定左侧节点，找满足条件的右节点
        // 向右移动左侧节点，则右侧节点只能继续往右移动
        Arrays.sort(nums);
        int len = nums.length;
        int left = 0;
        int right = 1;
        int res = 0;
        while(left < len && right < len) {
            right = Math.max(right, left + 1); // 保证 right 始终在 left 左边
            while(right < len && nums[right] - nums[left] < k) {
                right ++;
            }
            // right >= len || [right] - [left] >= k
            if(right == len) {
                return res;
            }
            if(nums[right] - nums[left] == k) {
                res ++;
                // 右侧指针去重
                while(right < len - 1 && nums[right] == nums[right + 1]) {
                    right ++;
                }
                if(right == len) {
                    return res;
                }
            }
            // 移动左指针，去除重复左指针
            while(left < right && nums[left] == nums[left + 1]) {
                left ++;
            }
            // [left] != [left + 1]
            left ++; 
        }
        return res;
    }
}

---

输出 1

---

解法 2 - Hash

class Solution {
    public int findPairs(int[] nums, int k) {
        // 思路：
        // 依次遍历每个元素，判断满足条件的数对是否存在
        // 数对有 2 种，一种是 +，一种是 -
        // 借助 hashset 去重
        int len = nums.length;
        int res = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i : nums) {
            if(!map.containsKey(i)) {
                map.put(i, 1);
            } else {
                int count = map.get(i);
                count ++;
                map.put(i, count);
            }
        }
        for(int i : nums) {
            if(!map.containsKey(i)) {
                continue; // 如果该下标元素已经统计过，那么就会被删除
            }
            // k == 0 分情况讨论
            if(k == 0) {
                if(map.containsKey(i) && map.get(i) > 1) {
                    res ++; // 不只有自己，说明有其他下标等值元素
                }
                map.remove(i); // 当前元素相关数对已经全部找完，删除该下标
            } else {
                // k > 0
                if(map.containsKey(i + k)) {
                    res ++;
                } 
                if(map.containsKey(i - k)) {
                    res ++;
                }
                map.remove(i);
            }
        }
        return res;
    }
}

---

输出