Leetcode 2364. Count Number of Bad Pairs

문제

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.

• 숫자 쌍의 인덱스 (i, j) 에 대해 i < j 일때, j - i != nums[j] - nums[i] 인 경우 나쁜 쌍으로 취급한다.
• 주어진 nums 배열에서 나쁜 쌍의 갯수를 리턴하시오

예시

[1, 2, 3, 4, 5]

• 모든 쌍이 나쁜 쌍이 아니다.
• 고로 0

제한

• $1 <= nums.length <= 10^5$
• $1 <= nums[i] <= 10^9$

풀이법

• 일단 자신의 index가 곧 자신이 쌍의 끝에 오는 쌍을 만들수 있는 갯수임을 기억한다.
  Ex. index 1번 은 (0, 1) 1개의 쌍을 만들수 있다.
• 나쁘지 않은 쌍의 조건은 j - i == nums[j] - nums[i] 인데 이는
  • j - nums[j] == i - nums[i] 로 바꿔 표현할수 있다.
  • 이렇게 되면 한 값으로 추적이 가능해진다.
• 딕셔너리에 i - nums[i]의 갯수를 추적해 만들수 있는 쌍의 갯수 - 좋은 쌍의 갯수 만큼을 정답에 더한다.

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        d = defaultdict(int)

        ans = 0

        for i, n in enumerate(nums):
            ans += i - d[i - n]
            d[i - n] += 1

        return ans