2024.03.01 - Count Number of Bad Pairs

[wlsgh7608]

문제 - 링크

문제 풀이

• bad pair 정의 if i < j && j - i != nums[j] - nums[i]
• bad pair의 쌍 개수 구하기

�good pair 구하기

• 우리는 bad pair의 개수를 바로 구하기 힘드므로 good pair을 구한 뒤 전체 - good pair 이용

        // good pair
        // i - j == nums[i] - nums[j]
        // i - nums[i] == j - nums[j]

코드

class Solution {
  public long countBadPairs(int[] nums) {
        int N = nums.length;
        int[] diff = new int[N];

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

        // good pair
        // i - j == nums[i] - nums[j]
        // i - nums[i] == j - nums[j]

        long tot = (long) N * (N - 1) / 2;
        long goodCnt = 0;
        HashMap<Integer, Integer> hm = new HashMap<>();
        for (int i = 0; i < N; i++) {
            if (hm.containsKey(diff[i])) {
                goodCnt += hm.get(diff[i]);
            }
            hm.put(diff[i], hm.getOrDefault(diff[i], 0) + 1);
        }


        return tot - goodCnt;
    }
}

시간, 공간 복잡도

• 시간 복잡도 : O(N)
• 공간 복잡도 : O(N)

실행 시간