LeetCode532 数组中的 k-diff 数对

发表于 | 分类于 |
字数统计: 407 | 阅读时长 ≈ 1

链接： https://leetcode.cn/problems/k-diff-pairs-in-an-array/

题意

给你一个整数数组 nums 和一个整数 k，请你在数组中找出 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目
k-diff 数对定义为一个整数对 (nums[i], nums[j]) 满足两数之差为k

解法

想到的两种解法

第一种是用哈希表存储每个数字出现情况，然后判断一下以它作为其中一个数的k-diff另一个数有没有出现过
统计一下出现的情况 k=0的情况需要单独处理一下
代码中有一些细节

第二种做法是双指针（尺取法）
首先排序，然后计算根据两数之差的情况移动指针
还需要考虑去重

代码

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        int cnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            int val = (mp[nums[i] - k] > 0) + (mp[k + nums[i]] > 0);
            if (val) {
                if (mp[nums[i]] == 0){
                    // cout << nums[i] << ' ' << i << ' ' << val << endl;
                    cnt += val;
                }
            }
            mp[nums[i]]++;
        }
        if (k == 0) {
            for (auto idx: mp) {
                if (idx.second > 1) cnt++;
            }
        }
        return cnt;
    }
};

尺取法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int l = 0, r = 1, cnt = 0;
        while(r < nums.size()) {
            int val = nums[r] - nums[l];
            if (val > k) {
                l++;
            }
            else if (val < k) {
                r++;
            }
            else {
                cnt++;
                l++;
            }
            while(l > 0 && l < nums.size() && nums[l] == nums[l - 1]) l++;
            if (r <= l) r = l + 1;
        }
        return cnt;
    }
};