Java O(n) solution - one Hashmap, easy to understand


  • 77
    public class Solution {
        public int findPairs(int[] nums, int k) {
            if (nums == null || nums.length == 0 || k < 0)   return 0;
            
            Map<Integer, Integer> map = new HashMap<>();
            int count = 0;
            for (int i : nums) {
                map.put(i, map.getOrDefault(i, 0) + 1);
            }
            
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                if (k == 0) {
                    //count how many elements in the array that appear more than twice.
                    if (entry.getValue() >= 2) {
                        count++;
                    } 
                } else {
                    if (map.containsKey(entry.getKey() + k)) {
                        count++;
                    }
                }
            }
            
            return count;
        }
    }
    

  • 6
    T

    Perfect. Easy to read and understand > one-liner solution. Thanks for this.


  • 0
    T

    @tankztc awesome


  • 0
    C

    How did you come up with such concise solution? I understand your solution, but how did you know that absolute diff does not need to calculate both + and -. I didn't think about it till I saw your solution!
    I used a map and a set and the logic is much more complex. Thank you!

    int findPairs(vector<int>& nums, int k) {
        unordered_map<int, unordered_set<int>> numToIdx;
        unordered_set<int> used;
        
        for(int i=0; i<nums.size(); i++){
            numToIdx[nums[i]].insert(i);
        }
        
        int res = 0;
        
        if (k<0)
           return res;
        
        for (int i=0; i<nums.size(); i++){
            if (used.find(nums[i])!=used.end())
                continue;
            int plusK = nums[i]+k, minusK = nums[i] - k;
            
            if (numToIdx.find(plusK)!=numToIdx.end()&&numToIdx[plusK].find(i)==numToIdx[plusK].end()){
                res++;
            }
            
            if (plusK!=minusK && numToIdx.find(minusK)!=numToIdx.end()&&numToIdx[minusK].find(i)==numToIdx[minusK].end()){
                res++;
            }
            
            if (k==0 &&numToIdx[plusK].size()>=2){
                res++;
            }
            numToIdx.erase(nums[i]);
            used.insert(nums[i]);
        }
        
        return res;
    }

  • 6

    @coder2
    Since duplicates are not allowed in the solution, we only need to compute + or - to build results. Suppose we have 3 and 5 with k == 2, we know that 3 + 2 == 5 by using PLUS operation. However, when we visit 5, if we consider 5 - 2 == 3 by using MINUS operation, there will be a duplicate. Hope it helps.


  • 2
    I

    one pass:

            if (k < 0) return 0; // absolute difference
            Set<Integer> seen = new HashSet<>(), used = new HashSet<>();
            for (int num : nums) {
                if (seen.contains(num + k)) {
                    if (!used.contains(num)) used.add(num);
                }
                if (k != 0 && seen.contains(num - k)) {
                    if (!used.contains(num - k)) used.add(num - k);
                }
                seen.add(num);
            }
            return used.size();
    

  • 4
    N

    Similar solution

    public class Solution {
        public int findPairs(int[] nums, int k) {
            Map<Integer,Integer> mp = new HashMap<Integer,Integer>();
            if(k<0)
                return 0;
                
            for(int i=0;i<nums.length;i++) {
                mp.put(nums[i],i);
            }
            
            int cnt=0;
            for(int i=0;i<nums.length;i++) {
                if(mp.containsKey(k+nums[i]) && mp.get(k+nums[i])!=i) {
                    cnt++;
                    mp.remove(k+nums[i]);
                }
            }
            return cnt;
        }
    }
    

  • 0

    Thanks for sharing! But duplicate solution need to be handled, right?

        public int findPairs(int[] nums, int k) {
            if (nums.length == 0 || k < 0) return 0;
            Map<Integer,Integer> map = new HashMap<>();
            for (int num : nums) {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
            
            int cnt = 0;
            for (int num : nums) {
                if (k == 0) {
                    if (map.containsKey(num) && map.remove(num) >= 2) cnt++;
                } else {
                    if (map.remove(num + k) != null) cnt++;
                }
            }
            return cnt;
        }
    

  • 0
    Y

    Thank you for your wonderful solution. Howerver, I think when k=0, the variable "count" is not simply the time a number occurs. Maybe I can't understand the question? For example, when there are four "1" in the array, I think the answer is 6 (4*3/2).


  • 1

    @Yushi_123 the answer is 2


  • 0
    N
    public class Solution {
        public int findPairs(int[] nums, int k) {
            if(nums.length == 0 || k < 0) return 0;
            int count = 0;
            HashSet<Integer> set = new HashSet<Integer>();
            HashSet<Integer> used = new HashSet<Integer>();
            if(k==0){
                for(int num:nums){
                    if(set.contains(num) && !used.contains(num)){
                        count++;
                        used.add(num);
                    }else{
                        set.add(num);
                    }
                }
                return count;
            }
            for(int num:nums){
                set.add(num);
            }
            for(int num: nums){
                if(!used.contains(num) && set.contains(num+k)){
                    count++;
                    used.add(num);
                }
            }
            return count;
        }
    }
    

  • 0
    A

    @NaomiJingLi This is O(n) only when hashmap uses perfect hashing. Interestingly, your code doesn't run in O(n)! Please, remove the disinformation or implement a perfect hashmap.


  • 1
    U

    Easy to understand,Fantastic solution


  • 0
    A

    No need for the "nums == null || nums.length == 0 ||" in the beginning

    :)


  • 1
    K

    One pass and easy logic, with explanation:

    public int findPairs(int[] nums, int k) {
            if(k < 0) return 0;
    
            int pairs = 0;
            HashMap<Integer, Integer> map = new HashMap<>();
    
            for(int n: nums) {
                int count = map.getOrDefault(n, 0);
                map.put(n, count + 1);
    
                if(k != 0 && count == 0) {
                    // if k != 0 and this is the first time meeting this number, check n - k and n + k
                    if(map.containsKey(n - k)) {
                        pairs++;
                    }
    
                    if(map.containsKey(n + k)) {
                        pairs++;
                    }
                } else if(k == 0 && count == 1) {
                    // if k == 0, only when we have met the number twice do we count it as a pair
                    pairs++;
                }
            }
    
            return pairs;
        }
    
    

  • 0
    F

    @cdai Since you loop over the array, so you need to handle duplicates. But if you loop over the keyset of map from map.entrySet(), there are no duplicate appeared because each number will only appear once.


  • 0
    F

    Actually, there are no need to handle the cases nums == null || nums.length == 0 at the beginning. those cases will not step into any loop, so the default count value will be returned.


  • 0
    D

    Using hashMap and hashSet

    public class Solution {
        
        
        public int findPairs(int[] nums, int k) 
        {
            if (nums == null || nums.length == 0 || k < 0) { return 0; }
            
            // num --- count pair
            Map<Integer, Integer> map = new HashMap<>();
            // convert each pair to string, e.g (a,b) => "ab", smaller number first (a < b)
            Set<String> set = new HashSet<>();
            
            for (int n : nums) { map.put(n, map.getOrDefault(n, 0) + 1); }
            
            for (int n : nums)
            {
                int less = n - k;
                int more = n + k;
                if (less == more)
                {
                    if (map.get(n) > 1) { set.add(n + "" + n); }
                }
                else
                {
                    if (map.containsKey(less)) { set.add(less + "" + n); }
                    if (map.containsKey(more)) { set.add(n + "" + more); }
                }
    
                // remove n in map if count is 0
                int val = map.get(n);
                if (val - 1 == 0) { map.remove(n); }
                else { map.put(n, val - 1); }
            }
    
            return set.size();
        }
    }
    

  • 0
    D

    same idea
    '''
    public int findPairs(int[] nums, int k) {
    if(nums.length==0||k<0)return 0;
    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    int count = 0;
    map.put(nums[0],1);
    for(int i =1;i<nums.length;i++){
    if(map.containsKey(nums[i])){
    if(k==0&&map.get(nums[i])==1)count++;
    map.put(nums[i],2);
    continue;
    }
    if(map.containsKey(nums[i]-k))count++;
    if(map.containsKey(nums[i]+k))count++;
    map.put(nums[i],1);
    }
    return count;
    }
    '''


  • 0
    D
       public int findPairs(int[] nums, int k) {
            if(nums.length==0||k<0)return 0;
            Map<Integer,Integer> map = new HashMap<Integer,Integer>();
            int count = 0;
            map.put(nums[0],1);
            for(int i =1;i<nums.length;i++){
                if(map.containsKey(nums[i])){
                    if(k==0&&map.get(nums[i])==1)count++;
                    map.put(nums[i],2);
                    continue;
                }
                if(map.containsKey(nums[i]-k))count++;
                if(map.containsKey(nums[i]+k))count++;
                map.put(nums[i],1);
            }
            return count;
        }
    

Log in to reply
 

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