# [C++] [Java] Clean Code with Explanation [set] [map]

• C++

``````class Solution {
public:
/**
* for every number in the array:
*  - if there was a number previously k-diff with it, save the smaller to a set;
*  - and save the value-index to a map;
*/
int findPairs(vector<int>& nums, int k) {
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();
}
};
``````

Java

``````public class Solution {
public int findPairs(int[] nums, int k) {
if (k < 0) { return 0; }

Set<Integer> starters = new HashSet<Integer>();
Set<Integer> uniqs = new HashSet<Integer>();
for (int i = 0; i < nums.length; i++) {
if (uniqs.contains(nums[i] - k)) starters.add(nums[i] - k);
}

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

• Not sure why you want to save the index

• Thanks for sharing your idea, I like this one.

Some comments: k is absolute difference, which means k >= 0. We want to find pair (a,b), which satisfies a-b=diff. This implies a>=b, and a=k+b, b=a-k. The unordered_map `indices` is act as the Hash Table in the Two Sum problem, and unordered_set `starters` is used to store the smaller number of the pair, which is the `a` in above illustration.

But I think we don't need to store the index of the number, we can just use 2 sets to do this. Here is my Python version,

``````class Solution(object):
def findPairs(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
if not nums or k < 0:
return 0
smaller_num_set = set()
for num in nums:
return len(smaller_num_set)
``````

• @NoAnyLove You are right. The latest index wasn't necessary here. I was about to save the number of indices, so that we can handle unique pairs, then I realize that the problem doesn't care the uniques, so I left the map there and saved the latest instead. I have updated the C++ solution to save number of indices, and Java solution to save only value. Thanks!

• Thanks for your concise code. Here's my java solution, but it is really slow, O(n*n) complexity :--(

``````	public static int findPairs(int []nums, int k){

int count=0;
Arrays.sort(nums);//sort at first
for(int i=0;i<nums.length-1;i++){
if(i>0 && nums[i]==nums[i-1]){// first loop, skip the same elements
continue;
}
for(int j=i+1;j<nums.length;j++){
//second loop, skip the same elements
if(j>i+1 && nums[j]==nums[j-1]){
continue;
}
//if the firts and second elements' diff is k, we count
if(nums[j]-nums[i]==k){
count++;
}
}
}
return count;
}``````

• it's no need to deal with k==0, really great solution :)

• @NoAnyLove
IMHO, since k is absolute difference, we only need to check one direction: either num-k or num+k, like if you just go forward or go backward, you won't pass a place twice.
here's mine, little verbose though:
if(nums==null||nums.length==0||k<0)
return 0;
int count=0;
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
}
if(k==0){
for(Integer val:map.values()){
if(val>1)
count++;
}
} else{
for(Integer key:map.keySet()){
if(map.containsKey(key+k))
count++;
}
}
return count;

• Hi @biyand , I'm afraid that's not true.

You should notice that if we only check one direction, we need to first go through `nums` and put each element into a Map. As a result, we actually need to traverse the array twice. While @alexander 's solution only need to traverse `nums` once, if it checks on both direction. Although it conducts twice lookup for each element, it is still a little bit faster than traversing twice.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.