BiruLyu
7/5/2017 - 10:03 PM

## 532. K-diff Pairs in an Array(1st).java

``````import java.util.Map.Entry;

public class Solution {
public int findPairs(int[] nums, int k) {
if (nums == null || nums.length == 0 || k<0)	return 0;

Arrays.sort(nums);
int cnt = 0, left = 0, right = 1;

while (left < nums.length && right < nums.length)	{
//每次檢查指標是否重疊，以及距離小於K移動右邊指標
if (left == right || nums[left] + k > nums[right])
right++;
//反之距離大於K移動左邊指標
else if (nums[left] + k < nums[right])
left++;
else	{
//找到符合的區間
cnt++;
left++;	//移動指標
//檢查是否有重複直存在
while (left < nums.length && nums[left] == nums[left-1])	left++;
right++;
}

}

return cnt;

}
}``````
``````public class Solution {
public int findPairs(int[] nums, int k) {
if (nums == null || nums.length < 1 || k < 0) return 0;
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
int res = 0;
if (k == 0) {
for (int value : map.values()) {
if (value > 1) res++;
}
return res;
} else if(k > 0){
for (int num : map.keySet()) {
if(map.containsKey(num + k)) res++;
}
return res;
}
return res;
}
}``````
``````public class Solution {
public int findPairs(int[] nums, int k) {
if(k < 0) return 0;
int lower = Integer.MIN_VALUE;
Arrays.sort(nums);
int i = 0, j = 0;
int diff = 0;
int count = 0;
while( i < nums.length && j < nums.length) {
diff = nums[j] - nums[i];
if(diff == k && i != j) {
if(nums[i] > lower) {
count++;
lower = nums[i];
}
i++;
} else if(diff > k) i++;
else j++;
}
return count;
}
}``````