How do I approach the 'Count Equal and Divisible Pairs in an Array' problem?

Start by using a brute-force approach that checks all pairs of indices. Ensure both the equality condition and divisibility by k are satisfied.

What is the time complexity of the brute-force solution?

The time complexity is O(n^2) because the solution involves checking all pairs of indices in the array.

Are there optimization strategies for larger arrays?

Yes, optimization can be explored by using hash maps, segmenting the array, or reducing unnecessary checks based on divisibility rules.

How do I handle edge cases in this problem?

Consider arrays with no equal pairs, arrays where all elements are the same, and variations of k, ensuring all possible scenarios are covered.

What other problems have a similar pattern to 'Count Equal and Divisible Pairs in an Array'?

Problems involving pairwise comparisons and divisibility often require array-driven solutions, like finding pairs that satisfy certain mathematical conditions.

#2176

Easy

auto_awesome数组·driven

LeetCode 题解工作台

统计数组中相等且可以被整除的数对

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k ，请你返回满足 0 ， nums[i] == nums[j] 且 (i * j) 能被 k 整除的数对 (i, j) 的数目。示例 1：输入： nums = [3,1,2,2,2,1,3], k = 2 输出： 4 解…

数组

题目描述

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k ，请你返回满足 0 <= i < j < n ，nums[i] == nums[j] 且 (i * j) 能被 k 整除的数对 (i, j) 的数目。

示例 1：

输入：nums = [3,1,2,2,2,1,3], k = 2
输出：4
解释：
总共有 4 对数符合所有要求：
- nums[0] == nums[6] 且 0 * 6 == 0 ，能被 2 整除。
- nums[2] == nums[3] 且 2 * 3 == 6 ，能被 2 整除。
- nums[2] == nums[4] 且 2 * 4 == 8 ，能被 2 整除。
- nums[3] == nums[4] 且 3 * 4 == 12 ，能被 2 整除。

示例 2：

输入：nums = [1,2,3,4], k = 1
输出：0
解释：由于数组中没有重复数值，所以没有数对 (i,j) 符合所有要求。

提示：

1 <= nums.length <= 100
1 <= nums[i], k <= 100

lightbulb

解题思路

方法一：枚举

我们先在 $[0, n)$ 的范围内枚举下标 $j$ ，然后在 $[0, j)$ 的范围内枚举下标 $i$ ，统计满足 $\textit{nums}[i] = \textit{nums}[j]$ 且 $(i \times j) \bmod k = 0$ 的数对个数。

时间复杂度 $O(n^2)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        ans = 0
        for j, y in enumerate(nums):
            for i, x in enumerate(nums[:j]):
                ans += int(x == y and i * j % k == 0)
        return ans

speed

复杂度分析

指标	值
时间	O(n^2)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Understanding how to handle pairs and divisibility checks can indicate a solid grasp of basic iteration and array manipulation.
question_mark
The ability to discuss potential optimizations shows the candidate can think beyond brute-force solutions.
question_mark
Evaluating edge cases reflects attention to detail and robustness in solution design.

warning

常见陷阱

外企场景

error
Forgetting to check the condition i < j and mistakenly considering pairs where i >= j.
error
Overlooking divisibility by k when checking the pairs, leading to incorrect counts.
error
Not handling arrays with all distinct elements properly, where no pairs should meet the conditions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array is sorted? Can we optimize the solution by leveraging the order?
arrow_right_alt
What if the value of k is large, can we use modular arithmetic to speed up the process?
arrow_right_alt
How would the problem change if instead of indices, we were to check the product of values themselves?

help

常见问题

外企场景

继续练习

#2179 统计数组中好三元组数目 #2172 数组的最大与和 #2171 拿出最少数目的魔法豆