[LeetCode] 2364. Count Number of Bad Pairs

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

leetcode - Count Number of Bad Pairs

문제 유형: 투 포인터, 해시, 정렬, 수학

문제 난이도: Medium

 

문제

You are given a 0-indexed integer array nums. A pair of indices (i, j) is a bad pair if i < j and j - i != nums[j] - nums[i].

Return the total number of bad pairs in nums.

 

0-indexed의 정수 배열 nums가 주어진다.

(i, j)페어는 다음 조건을 만족하면 나쁜 페어이다: if i < j and j - i != nums[j] - nums[i].

나쁜 페어의 개수를 구하시오.

 

풀이

전체 페어의 수에서 좋은 페어의 수를 구해서 빼는 방법이 있다.

우선, 나쁜 페어의 조건을 재해석하면, 서로 다른 두 요소의 인덱스차와 값의 차가 달라야 한다는 것이다.

즉, 인덱스차와 값의 차가 같으면 좋은 페어이다.

현재 수의 값에 각 인덱스만큼 빼면, 이제는 값이 같으면 좋은 페어이다.

정렬해서 그룹의 개수를 세거나, 해시맵을 통해서 그 수를 갖는 그룹의 수를 구해서 모든 경우의 수(n*(n-1)/2)에서 빼주면 된다.

 

코드

C++

class Solution {
public:
    long long countBadPairs(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < nums.size(); ++i) {
            nums[i] -= i;
        }

        long long ans = (long long)n * (n - 1) / 2;

        sort(nums.begin(), nums.end());
        for(int left = 0; left < n; ++left) {
            int right = left;
            while(right < n && nums[right] == nums[left]) right++;
            int diff = right - left;
            if(right - left >= 2) {
                ans -= (long long)diff*(diff-1)/2;
            }
            left = right-1;
        }

        return ans;
    }
};

 

Go

func countBadPairs(nums []int) int64 {
    n := len(nums)
    ans := int64(n) * int64(n-1) / 2

    for i := 0; i < n; i++ {
        nums[i] -= i
    }

    sort.Slice(nums, func(i, j int) bool {
        return nums[i] < nums[j]
    })

    for left := 0; left < n; left++ {
        right := left;
        for right < n && nums[right] == nums[left] {
            right++
        }
        diff := int64(right - left)
        if diff >= 2 {
            ans -= diff*(diff-1)/2
        }
        left = right-1
    }
    return ans
}