1512. Number of Good Pairs

naive

T: O(n^2)

S: O(1)

class Solution {
    public int numIdenticalPairs(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    count++;
                }
            }
        }
        return count;
    }
}

use hashmap

T: O(n)

S: O(n)

class Solution {
    public int numIdenticalPairs(int[] nums) {
        int count = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                count += map.get(nums[i]);
            }
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        return count;
    }
}

/*
   
[1,2,3,1,1,3]
 
 pair is 
 
(0,3), (0,4), (3,4), (2,5)
 1,1.   1,1    1,1    3,3
 
  0     3
 [1,2,3,1] means (0,3) can be a pair, when iterate to index 3 ->  can find map has index 0 is 1
 
  0.1 2 3 4      
 [1,2,3,1,1    means (0,4), (3,4)  can be pairs
 
 when iterate to 4 -> 4 can find map has 0, 3 is 1
 
*/