class Solution {
public:
long long countBadPairs(vector<int>& nums) {
}
};
2364. 统计坏数对的数目
给你一个下标从 0 开始的整数数组 nums 。如果 i < j 且 j - i != nums[j] - nums[i] ，那么我们称 (i, j) 是一个 坏数对 。
请你返回 nums 中 坏数对 的总数目。
示例 1：
输入：nums = [4,1,3,3] 输出：5 解释：数对 (0, 1) 是坏数对，因为 1 - 0 != 1 - 4 。 数对 (0, 2) 是坏数对，因为 2 - 0 != 3 - 4, 2 != -1 。 数对 (0, 3) 是坏数对，因为 3 - 0 != 3 - 4, 3 != -1 。 数对 (1, 2) 是坏数对，因为 2 - 1 != 3 - 1, 1 != 2 。 数对 (2, 3) 是坏数对，因为 3 - 2 != 3 - 3, 1 != 0 。 总共有 5 个坏数对，所以我们返回 5 。
示例 2：
输入：nums = [1,2,3,4,5] 输出：0 解释：没有坏数对。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 109原站题解
golang 解法, 执行用时: 164 ms, 内存消耗: 12.8 MB, 提交时间: 2023-03-09 18:03:58
func countBadPairs(nums []int) int64 {
n := len(nums)
ans := n * (n - 1) / 2
cnt := map[int]int{}
for i, num := range nums {
ans -= cnt[num-i] // 有 cnt[num-i] 个相同的
cnt[num-i]++
}
return int64(ans)
}
python3 解法, 执行用时: 116 ms, 内存消耗: 37 MB, 提交时间: 2023-03-09 18:03:17
'''
转为 nums[i] -i == nums[j] - j 的对数，用总数减去即可
'''
class Solution:
def countBadPairs(self, nums: List[int]) -> int:
n = len(nums)
cnt = Counter([num - i for i, num in enumerate(nums)])
ans = n * (n-1) // 2
for _, v in cnt.items():
ans -= v*(v-1)//2
return ans
python3 解法, 执行用时: 212 ms, 内存消耗: 35.8 MB, 提交时间: 2023-03-09 17:58:14
'''
转为 nums[i] -i == nums[j] - j 的对数，用总数减去即可
'''
class Solution:
def countBadPairs(self, nums: List[int]) -> int:
n, cnt = len(nums), Counter()
ans = n * (n - 1) // 2
for i, num in enumerate(nums):
ans -= cnt[num - i] # 有 cnt[num - i] 个相同的
cnt[num - i] += 1
return ans