网络架构图和拓扑图_山西搜索引擎优化_seo技术培训东莞_广西网站建设制作

记录

2025.4.18

题目：

思路：

将j-i!=nums[j]-nums[i]变形成j-nums[j]!=i-nums[i]。
遍历数组，用哈希表记录。

解题步骤：

1.初始化哈希表：HashMap<Integer, Integer> mp用于记录每个键值的出现次数。

2.遍历数组：对于每个元素nums[i]，计算其键值nums[i] - i。

3.计算坏对数量：当前元素i可以与前面i个元素中的i - count个元素形成坏对，其中count是当前键值在哈希表中的出现次数。

4.更新哈希表：每次处理完当前元素后，更新哈希表中当前键值的出现次数。

代码：

class Solution {public long countBadPairs(int[] nums) {HashMap<Integer, Integer> mp = new HashMap<>();long res = 0;for (int i = 0; i < nums.length; i++) {int key = nums[i] - i;res += i - mp.getOrDefault(key, 0);mp.put(key, mp.getOrDefault(key, 0) + 1);}return res;}
}

复杂度：

N（N）
N（N）