Leetcode 3649. Number of Perfect Pairs

• Leetcode 3649. Number of Perfect Pairs
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3649. Number of Perfect Pairs

1. 解题思路

这一题首先我们需要明白，选择的两个数的实际的位置与结果是没有关系的，因此，我们不妨将所有的数字顺序排列，然后令取到的两个数$a,b$满足大小关系$a\le b$。

此时，我们分类讨论，考察$a$在不同的情况下对应的满足条件的$b$的取值范围，有如下情况：

然后，我们只需要考察每一个元素作为$a$的情况下对应的$b$的取法个数，然后将其相加即可。

2. 代码实现

给出python代码实现如下：

class Solution:def perfectPairs(self, nums: List[int]) -> int:nums = sorted(nums)n = len(nums)ans = 0for i, a in enumerate(nums):if a < 0:l = bisect.bisect_left(nums, -a/2)r = bisect.bisect_right(nums, -2*a)if r < n and nums[r] == -2*a:r += 1ans += r-ll = max(bisect.bisect_left(nums, a), i)r = bisect.bisect_right(nums, a/2)if r < n and nums[r] == a/2:r += 1ans += r-l-1else:l = max(bisect.bisect_left(nums, a), i)r = bisect.bisect_right(nums, 2*a)if r < n and nums[r] == 2*a:r += 1ans += r-l-1return ans

提交代码评测得到：耗时963ms，占用内存30.88MB。