Leetcode 2563. Count the Number of Fair Pairs

Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs.

A pair (i, j) is fair if:

0 <= i < j < n, and
lower <= nums[i] + nums[j] <= upper

• 배열이 주어진다.
• 다른 index를 가지면서 두 합이 lower와 같거나 크고 upper과 같거나 작은 쌍의 개수를 구하여라
• 단, index의 위치만 뒤바뀐 pair는 세지 않는다.
  • Ex. [1, 2] 와 [2, 1] 은 따로 세지 않음

예시

[0,1,7,4,4,5]

• 0, 3 페어
• 0, 4 페어
• 0, 5 페어
• 1, 3 페어
• 1, 4 페어
• 1, 5 페어

총 6개의 쌍이 존재한다.

제한

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

풀이

• left를 기준으로 하여 lower-left와 upper-left 범위 내 숫자들의 적절한 갯수를 구한다.

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()

        ans = 0

        for index, left in enumerate(nums):
            l = bisect_left(nums, lower - left)
            r = bisect_right(nums, upper - left)
            l = max(l, index + 1)
            diff = r - l
            ans += max(diff, 0)

        return ans