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


  • 11

    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);
                if (uniqs.contains(nums[i] + k)) starters.add(nums[i]);
                uniqs.add(nums[i]);
            }
    
            return starters.size();
        }
    }
    

  • 1
    H

    Not sure why you want to save the index


  • 1
    N

    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
            already_seen = set()
            smaller_num_set = set()
            for num in nums:
                if num-k in already_seen:
                    smaller_num_set.add(num - k)
                if num+k in already_seen:
                    smaller_num_set.add(num)
                already_seen.add(num)
            return len(smaller_num_set)
    

  • 0

    @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!


  • 0
    G

    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;
    	}

  • 0
    S

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


  • 0
    B

    @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;


  • 0
    N

    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.


Log in to reply
 

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