leetcoed 532 K-diff Pairs in an Array

SimpleTriangle 发布于2019-08-15 13:53 / 2958人阅读

摘要：由于无法处理相同的操作，所依对于的时候，我采用了进行操作。为时，对于每一次遍历，找到这个值是否已经存在在里，同时获取这个值出现过的次数。

题目详情

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.这道题的意思是，输入一个整数数组和一个整数k，我们需要找出数组中绝对值差正好为k的不重复的整数对儿
Example 1:
Input: [3, 1, 4, 1, 5], k = 2
Output: 2
这个例子中有两个不同的整数对, (1, 3)和(3, 5).
Example 2:
Input:[1, 2, 3, 4, 5], k = 1
Output: 4
这个例子里有四个不同的整数对(1, 2), (2, 3), (3, 4)和(4, 5).
Example 3:
Input: [1, 3, 1, 5, 4], k = 0
Output: 1
这个例子里有一个符合要求的整数对（1，1）

想法

这道题我分两种情况进行的讨论，一种是k不为0的时候，我通过新建一个hashset来完成计算。

由于hashset无法处理相同key的操作，所依对于k＝＝0的时候，我采用了hashmap进行操作。

k为0时，对于每一次遍历，找到这个值是否已经存在在hashmap里，同时获取这个值出现过的次数（value）。如果次数为1，那么我们获得了一个符合要求的整数对，如果次数大于1，那么说明这个整数对已经被统计过了，可以忽略。如果这个键值未曾出现在hashmap里，那么我们将其存入hashmap，将value赋值为1.

当k不为0时，我们遍历每一个元素，如果这个元素和当前set中的元素不重复的话，我们将这个元素存入set，然后判断在set中是否有满足和这个元素的绝对值相差为k的整数出现，如果有，构成一个整数对。

解法

        int res = 0;
        if(k < 0)return 0;
        if(k == 0){
            HashMap countZero = new HashMap();
            for(int i=0;i count = new HashSet();
            for(int num : nums){
                if(!count.add(num)){continue;}
                if(count.contains(num+k)){
                    res ++;
                } 
                if(count.contains(num-k)){
                    res ++;
                }
            }
            
        }
        return res;

GPU云服务器云服务器 in_array() in_array in_array()函数 in_array()示例代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68382.html

[LintCode] K-diff Pairs in an Array

Problem 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 nu...

Leck1e 2019-08-15 18:16 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
underscore.js 源码学习 array（未完待续）

摘要：如果为空的情况下，也为空返回，不为空返回为空，返回数组第一个元素返回包含数组前个元素的数组返回数组中除了最后一个元素外的其他全部元素。 // Array Functions // --------------- // Get the first element of an array. Passing **n** will return the first N ...

tomato 2019-08-23 17:04 评论0 收藏0
LeetCode 561：数组拆分 I Array Partition I

摘要：给定长度为的数组你的任务是将这些数分成对例如，使得从到的总和最大。提示是正整数范围在数组中的元素范围在解题思路其实就是把数组排序，然后按顺序每两个数既是一对，每对的第一个数累加之和即为所求。就是考一下各类排序算法的性能。文章全部来自公众号：爱写bug 算法是一个程序的灵魂。Given an array of 2n integers, your task is to group the...

gnehc 2019-08-16 18:28 评论0 收藏0