2364. 统计坏数对的数目
来源第 84 场双周赛 Q2难度中等分数1622
题目描述
给你一个下标从 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
解法
方法一:式子转换 + 哈希表
思考
坏数对满足 \(j-i \ne \textit{nums}[j]-\textit{nums}[i]\),即 \(i-\textit{nums}[i] \ne j-\textit{nums}[j]\)。 \(n \le 10^5\),应统计互补的好对。
从左到右扫描,当前下标 \(i\) 与此前同余 \(i-\textit{nums}[i]\) 的个数之差即新增坏对,再把该键加一。前缀计数避免双重循环。
根据题目描述,我们可以得知,对于任意的 \(i \lt j\),如果 \(j - i \neq \textit{nums}[j] - \textit{nums}[i]\),则 \((i, j)\) 是一个坏数对。
我们可以将式子转换为 \(i - \textit{nums}[i] \neq j - \textit{nums}[j]\)。这启发我们用哈希表 \(\textit{cnt}\) 来统计 \(i - \textit{nums}[i]\) 的出现次数。
遍历数组,对于当前元素 \(\textit{nums}[i]\),我们将 \(i - \textit{cnt}[i - \textit{nums}[i]]\) 加到答案中,然后将 \(i - \textit{nums}[i]\) 的出现次数加 \(1\)。
最后,我们返回答案即可。
时间复杂度 \(O(n)\),空间复杂度 \(O(n)\)。其中 \(n\) 为数组 \(\textit{nums}\) 的长度。
1 2 3 4 5 6 7 8 | |
1 2 3 4 5 6 7 8 9 10 11 | |
1 2 3 4 5 6 7 8 9 10 11 12 | |
1 2 3 4 5 6 7 8 9 | |
1 2 3 4 5 6 7 8 9 10 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |