What is a bad pair in the "Count Number of Bad Pairs" problem?

A bad pair is a pair of indices (i, j) such that i < j and the condition j - i != nums[j] - nums[i] holds true.

How can I optimize the solution for the "Count Number of Bad Pairs" problem?

By using array scanning with a hash table to track the differences between the index and value, you can optimize the solution to run in O(n) time complexity.

What is the time complexity of the "Count Number of Bad Pairs" solution?

The solution runs in O(n) time complexity due to the efficient array scanning and hash table usage.

What is the key idea for solving the "Count Number of Bad Pairs" problem?

The key idea is to count non-bad pairs first by leveraging the condition j - i = nums[j] - nums[i] and subtracting from the total possible pairs.

How do hash tables help solve the "Count Number of Bad Pairs" problem?

Hash tables store previously seen differences between indices and values, allowing you to efficiently count pairs that satisfy the condition for non-bad pairs.

#2364

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

统计坏数对的数目

给你一个下标从 0 开始的整数数组 nums 。如果 i 且 j - i != nums[j] - nums[i] ，那么我们称 (i, j) 是一个坏数对。请你返回 nums 中坏数对的总数目。示例 1：输入： nums = [4,1,3,3] 输出： 5 解释：数对 (0, 1…

数组哈希表数学计数

题目描述

给你一个下标从 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 <= 10⁵
1 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：式子转换 + 哈希表

根据题目描述，我们可以得知，对于任意的 $i \lt j$ ，如果 $j - i \neq \textit{nums}[j] - \textit{nums}[i]$ ，则 $(i, j)$ 是一个坏数对。

我们可以将式子转换为 $i - \textit{nums}[i] \neq j - \textit{nums}[j]$ 。这启发我们用哈希表 $cnt$ 来统计 $i - \textit{nums}[i]$ 的出现次数。

遍历数组，对于当前元素 $\textit{nums}[i]$ ，我们将 $i - 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

9

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        cnt = Counter()
        ans = 0
        for i, x in enumerate(nums):
            ans += i - cnt[i - x]
            cnt[i - x] += 1
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Candidate's ability to recognize the connection between index and value differences.
question_mark
Efficiency in counting bad pairs by leveraging hash tables.
question_mark
Understanding of transforming a complex problem into a counting problem.

warning

常见陷阱

外企场景

error
Not recognizing the need for a hash table to track index-value differences.
error
Misunderstanding the problem by attempting to check each pair directly with nested loops, leading to O(n^2) complexity.
error
Overlooking the importance of transforming the problem to count non-bad pairs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling larger arrays efficiently (up to length 10^5).
arrow_right_alt
Adjusting the solution for arrays containing negative numbers or large values.
arrow_right_alt
Finding the number of non-bad pairs instead of bad pairs.

help

常见问题

外企场景

继续练习

#2442 反转之后不同整数的数目 #2001 可互换矩形的组数 #1994 好子集的数目