1782.统计点对的数目

链接：1782.统计点对的数目
难度：Hard
标签：图、数组、双指针、二分查找、排序
简介：请你返回一个数组 answers ，其中 answers.length == queries.length 且 answers[j] 是第 j 个查询的答案。

题解 1 - cpp

• 编辑时间：2023-08-23
• 执行用时：836ms
• 内存消耗：181.42MB
• 编程语言：cpp
• 解法介绍：两个节点的边总和为 n[a]+n[b]-m[a][b] 要减去共有的边，先统计两个节点边和大于目标值的个数。

class Solution {
public:
    vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
        vector<int> nodes(n, 0);
        unordered_map<int, unordered_map<int, int>> m;
        for (auto &edge : edges) {
            int x = edge[0] - 1, y = edge[1] - 1;
            if (x > y) swap(x, y);
            nodes[x] += 1;
            nodes[y] += 1;
            m[x][y] += 1;
        }
        vector<int> res, list = nodes;
        sort(list.begin(), list.end());
        for (auto &query : queries) {
            int val = 0;
            for (int i = 0; i < n; i++) {
                int target = query - list[i], l = i + 1, r = n;
                while (l < r) {
                    int m = (l + r) / 2;
                    if (list[m] > target) r = m;
                    else l = m + 1;
                }
                val += n - l;
            }
            for (auto &item1 : m) {
                int x = item1.first;
                for (auto &item2 : item1.second) {
                    int y = item2.first, cnt = item2.second;
                    if (nodes[x] + nodes[y] > query && nodes[x] + nodes[y] - cnt <= query) val -= 1;
                }
            }
            res.push_back(val);
        }
        return res;
    }
};