1782. 统计点对的数目 双指针

1782. 统计点对的数目

给你一个无向图，无向图由整数 n  ，表示图中节点的数目，和 edges 组成，其中 edges[i] = [ui, vi] 表示 ui 和 vi 之间有一条无向边。同时给你一个代表查询的整数数组 queries 。

第 j 个查询的答案是满足如下条件的点对 (a, b) 的数目：

• a < b
• cnt 是与 a 或者 b 相连的边的数目，且 cnt 严格大于 queries[j] 。

请你返回一个数组 answers ，其中 answers.length == queries.length 且 answers[j] 是第 j 个查询的答案。

请注意，图中可能会有 重复边 。

示例 1：

输入：n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3]
输出：[6,5]
解释：每个点对中，与至少一个点相连的边的数目如上图所示。

示例 2：

输入：n = 5, edges = [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]], queries = [1,2,3,4,5]
输出：[10,10,9,8,6]

提示：

• 2 <= n <= 2 * 1e4
• 1 <= edges.length <= 1e5
• 1 <= ui, vi <= n
• ui != vi
• 1 <= queries.length <= 20
• 0 <= queries[j] < edges.length

 来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-pairs-of-nodes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

L

不会写，看了别人的思路。这题又属于复杂度卡的题，参考：度+遍历边

方法：双指针

即便看了思路，还是好难写
1，统计 from->(to,cnt) 每个点到另一个点对应的边数目
2. 统计所有点入度数目
3. 对所有数目排序
4. 双指针，定一点移动令一点，中间的为以一端为起点的可能的点对数目
5. 检查所有边（注意去重），如果原本加起来符合，减掉连线后的值不符合则从答案中移除

class Solution {
      public int[] countPairs(int n, int[][] edges, int[] queries) {
          Map<Integer,Map<Integer,Integer>>map = new HashMap<>(); //from->(to,cnt)
          int[] cnts = new int[n+1];

          for(int[] edge:edges){
              int a = edge[0];
              int b = edge[1];
              map.putIfAbsent(a,new HashMap<>());
              map.putIfAbsent(b,new HashMap<>());
              map.get(a).put(b,map.get(a).getOrDefault(b,0)+1);
              map.get(b).put(a,map.get(b).getOrDefault(a,0)+1);
              cnts[a]++;
              cnts[b]++;
          }
          int[] singles =Arrays.copyOf(cnts,cnts.length);

          Arrays.sort(singles);

          int len = queries.length;
          int[] ans = new int[len];
          for(int i = 0; i < len; i++){
              int left = 1;
              int right = n;
              while(left<right){
                  while (left<right&&singles[left]+singles[right]<=queries[i]) ++left;
                  if(left<right){
                      ans[i]+=right-left;
                  }
                  --right;
              }

              Set<Long> set = new HashSet<>();
              for(int []edge:edges){
                  int a = Math.min(edge[0],edge[1]);
                  int b = Math.max(edge[0],edge[1]);
                  long check = (long)a*(n+1)+b;
                  if(set.contains(check)) continue;
                  set.add(check);
                  int pre = cnts[a]+cnts[b];
                  int v= pre-map.getOrDefault(a,new HashMap<>()).getOrDefault(b,0);
                  if(pre>queries[i] && v<=queries[i])
                      ans[i] -= 1;
              }

          }

          return ans;
      }
  }