欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

532. K-diff Pairs in an Array

程序员文章站 2022-03-07 18:40:55
...
Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

Example :

Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

这道题我最开始的思路是将有差值的一对数放入到哈希表中,然后讲以后有差值的数在哈希表中进行比对,是key和value都进行比对,但是有错误,我也不知道哪里错误了,代码贴了出来,有谁知道了可以告诉我一下。

在最优解中,在查找中,在之前放入到indices哈希表中进行查找nums[i]+k || nums[i]-k的数,如果存在就是将有差值的一对数将其中的较小值放入到哈希表中,这样就避免了重复的一对数的出现,这种思路不太容易想到,但是也是时间复杂度也是比较小的,只需要将数组循环一遍。

532. K-diff Pairs in an Array


//
// Created by will on 2017/12/18.
//

#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <unordered_set>

using namespace std;

class Solution{
    public:
        int findPairs(vector<int>& nums, int k){

            /*
            map<int,int> map;
            int number = 0;
            for (int i = 0; i < nums.size(); ++i) {
                for (int j = i+1; j < nums.size(); ++j) {
                    if (abs(nums[i] - nums[j]) == k){

                        cout<<"k = "<<k<<" i and j :"<<nums[i]<<" . "<<nums[j]<<endl;
                        if(judgment(map, nums[i], nums[j])){
                            map.insert(pair<int, int>(nums[i],nums[j]));
                            number++;
                        }
                    }
                }
            }
            return number;
             */


            if (k < 0) {
                return 0;
            }
            unordered_set<int> starters;
            unordered_map<int, int> indices;
            for (int i = 0; i < nums.size(); i++) {
                if (indices.count(nums[i] - k)) {
                    starters.insert(nums[i] - k);
                }
                if (indices.count(nums[i] + k)) {
                    starters.insert(nums[i]);
                }

                indices[nums[i]] += 1;
            }

            return starters.size();
        }

        bool judgment(map<int,int>& map, int i, int j){
            if(map.count(i) && map[i] == j){
                return false;
            }
            else if (map.count(j) && map[j] == i){
                return false;
            }else{
                cout<<"inputnumbers:"<<i<<" "<<j<<endl;
                return true;
            }

        }
};

int main(){

    vector<int> nums = {6,2,9,3,9,6,7,7,6,4};
    Solution s;

    int num = s.findPairs(nums, 3);
    cout<<"the num is :"<<num;
    return 0;
}
相关标签: 532-K-dif