Leetcode
2020.05.04 10:04

532. K-diff Pairs in an Array

조회 수 728 추천 수 0 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄

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 1:

```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.
```

Example 2:

```Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).
```

Example 3:

```Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).
```

Note:

1. The pairs (i, j) and (j, i) count as the same pair.
2. The length of the array won't exceed 10,000.
3. All the integers in the given input belong to the range: [-1e7, 1e7].

```class Solution {
public int findPairs(int[] nums, int k) {
Map<String, Integer> hmap = new HashMap<>();

for(int i=0; i<nums.length-1; i++){
for(int j=i+1; j<nums.length; j++){
if(Math.abs(nums[i] - nums[j]) == k){
String key = Math.min(nums[i], nums[j]) + ":" + Math.max(nums[i], nums[j]);
hmap.put(key, hmap.getOrDefault(key,0)+1);
}
}
}

return hmap.size();
}
}```

```class Solution {
public int findPairs(int[] nums, int k) {
Set<Integer> hset = new HashSet<>();
int count = 0;

Arrays.sort(nums);

for(int i=0; i<nums.length; i++){
if(hset.contains(nums[i])){
continue;
}

if(findDiff(nums, i+1, nums.length-1, nums[i]+k) == true){
count++;
}
}
return count;
}

//binary search
public boolean findDiff(int[] nums, int start, int end, int target){
if(start > end){
return false;
}

int mid = start + (end-start)/2;
if(nums[mid] == target){
return true;
}else if(nums[mid] < target){
return findDiff(nums, mid+1, end, target);
}else{
return findDiff(nums, start, mid-1, target);
}
}
}```

```class Solution {
public int findPairs(int[] nums, int k) {
int count = 0;
long prev = Long.MAX_VALUE;

Arrays.sort(nums);
for(int i=0; i<nums.length; i++){
if(prev == nums[i]){
continue;
}
prev = nums[i];

if(findDiff(nums, i+1, nums.length-1, nums[i]+k) == true){
count++;
}
}
return count;
}

//binary search
public boolean findDiff(int[] nums, int start, int end, int target){
if(start > end){
return false;
}

int mid = start + (end-start)/2;
if(nums[mid] == target){
return true;
}else if(nums[mid] < target){
return findDiff(nums, mid+1, end, target);
}else{
return findDiff(nums, start, mid-1, target);
}
}
}```

?

 제목+내용제목내용댓글이름닉네임아이디태그
List of Articles
번호 분류 제목 글쓴이 날짜 조회 수
77 Programmers hashmap 2020.04.30 0
76 Programmers fib 2020.04.30 0
75 Programmers team game 2020.04.30 0
74 Leetcode 729. My Calendar I 2020.04.15 151
73 Leetcode 692. Top K Frequent Words 2020.04.15 153
72 Leetcode 75. Sort Colors 2020.04.14 155
71 Leetcode 443. String Compression 2020.04.25 156
70 Leetcode 347. Top K Frequent Elements 2020.04.14 158
69 Leetcode 23. Merge k Sorted Lists 2020.04.14 158
68 Leetcode 2. Add Two Numbers 2020.04.14 158
67 Leetcode 731. My Calendar II 2020.04.15 159
66 Leetcode 38. Count and Say 2020.04.25 160
65 Leetcode 946. Validate Stack Sequences 2020.04.08 162
64 Leetcode 350. Intersection of Two Arrays II 2020.04.28 163
63 Leetcode 7. Reverse Integer 2020.04.28 163
62 Leetcode 937. Reorder Data in Log Files 2020.04.25 165
61 Leetcode 852. Peak Index in a Mountain Array 2020.04.28 165
60 Leetcode 3. Longest Substring Without Repeating Characters 2020.04.09 172
59 Leetcode 973. K Closest Points to Origin 2020.04.15 172
58 Leetcode 62. Unique Paths 2020.04.09 173
Board Pagination Prev 1 2 3 4 Next
/ 4