LeetCode (C/C++, Java) 2364. Count Number of Bad Pairs

https://leetcode.com/problems/count-number-of-bad-pairs/

---

풀이

힌트 2를 보고 j - i !=  nums[j] - nums[i] 식은 nums[j] - j!= nums[i] - i와 같다는 걸 깨달았다.

해서 모든 원소에서 num[i] - i을 계산 후 해당 값을 map에 저장했다. 저장된 값을 순회하며 goodPairs의 개수를 구해 전체 개수에서 빼줬다.

---

C/C++ 코드

class Solution {
public:
    long long countBadPairs(vector<int>& nums) {
        map<long long, long long> m;

        long long len = nums.size();

        for (int i = 0; i < len; i++) {
            m[nums[i] - i]++;
        }

        long long goodPairs = 0;
        for (auto iter = m.begin(); iter != m.end(); iter++) {
            long long cnt = iter->second;
            goodPairs += (cnt * (cnt - 1) / 2);
        }

        long long allPairs = len * (len - 1) / 2;
        return allPairs - goodPairs;
    }
};

 

Java 코드

class Solution {
    public long countBadPairs(int[] nums) {
        Map<Long,Long> map = new HashMap<>();

        long len = nums.length;
        for (int i = 0; i < len; i++) {
            long diff = nums[i] - i;

            long val = map.getOrDefault(diff, 0L);
            map.put(diff, val + 1);
        }

        long goodPairs = 0L;
        for (long key : map.keySet()) {
            long cnt = map.get(key);
            if (cnt > 1)
                goodPairs += (cnt * (cnt - 1) / 2);
        }

        long allPairs = len * (len - 1) / 2;
        return allPairs - goodPairs;
    }
}