↓Skip to main content
  1. Posts/

LeetCode-2364 统计坏数对的数目

·1 min·
Table of Contents

LeetCode-2364 统计坏数对的数目 #

Solution 1 #

求 $j - i \not = nums[j] - nums[i]$ 的 “坏数对” 个数, 不妨改为求 $j - i = nums[j] - nums[i]$ 的 “好数对” 个数, 式子变形为 $j - nums[j] = i - nums[i]$ , 这样把二元性质转化成了一元的性质. 统计好数对个数时只需要考虑 $nums[i]$ 自身的值, 使用 $map$ 存储不同 $i - nums[j]$ 值的个数, 统计出 “好数对” 个数后用总数减去这个值就得到所求答案. 代码如下:

class Solution {
public:
    long long countBadPairs(vector<int>& nums) {
        long long n = nums.size();
        long long ans = n * (n - 1) / 2;
        unordered_map<int, long long> book;
        for (int i = 0; i < n; i++) {
            book[i - nums[i]]++;
        }
        for (auto it = book.begin(); it != book.end(); it++) {
            ans -= it->second * (it->second - 1) / 2;
        }
        return ans;
    }
};