【Leetcode】532. K-diff Pairs in an Array

思路: 成对的值不分先后,所以先对nums进行排序。 用一个set存储出现过的值,用于后续判断是否某个值已经有值与其成对。 分为两种情况: (1)k==0,即找出值相等的对数。 再用...

思路:


成对的值不分先后,所以先对nums进行排序。


用一个set存储出现过的值,用于后续判断是否某个值已经有值与其成对。


分为两种情况:


(1)k==0,即找出值相等的对数。


再用一个sameSet存储所有已成对的值,避免同一个值加入结果多次。只有sameSet中不含该值,且set中包含了该值,才能加入结果。


(2)k!=0,即找出差的绝对值为k的对数。


只有set中不包含该值但包含了该值-k,才能加入结果。

public class Solution {
    public int findPairs(int[] nums, int k) {
        int len = nums.length, result = 0;
        Arrays.sort(nums);
        Set<Integer> set = new HashSet<Integer>();
        Set<Integer> sameSet = new HashSet<Integer>();
        if (k != 0) {
            for (int i = 0; i < len; i++) {
                if (!set.contains(nums[i]) && set.contains(nums[i] - k)) 
                    result++;
                set.add(nums[i]);
            }
        }
        else {
            for (int i = 0; i < len; i++) {
                if (!sameSet.contains(nums[i]) && set.contains(nums[i])) {
                    result++;
                    sameSet.add(nums[i]);
                }
                set.add(nums[i]);
            } 
        }
        return result;
    } 
}

Runtime:44ms

你可能感兴趣的文章

相关问题

0 条评论

请先 登录 后评论
牟雪峰
牟雪峰

12 篇文章

作家榜 »

  1. admin 651 文章
  2. 粪斗 185 文章
  3. 王凯 92 文章
  4. 廖雪 78 文章
  5. 牟雪峰 12 文章
  6. 李沁雪 9 文章
  7. 全易 2 文章
  8. Jameshar 0 文章