LeetCode 2176: Count Equal and Divisible Pairs in an Array (Pair Enumeration with Index Product Filter)
LeetCode 2176ArrayBrute ForceInterviewToday we solve LeetCode 2176 - Count Equal and Divisible Pairs in an Array.
Source: https://leetcode.com/problems/count-equal-and-divisible-pairs-in-an-array/
English
Problem Summary
Given an integer array nums and an integer k, count pairs (i, j) such that i < j, nums[i] == nums[j], and (i * j) % k == 0.
Key Insight
The constraints are small enough for checking all index pairs. For each pair, we only need two conditions: values equal and product divisible by k.
Brute Force and Why It Works
Enumerate all i < j pairs. If values differ, skip. If values are equal, test divisibility of index product. This is straightforward and reliable for this problem size.
Optimal Algorithm Steps
1) Initialize answer ans = 0.
2) Loop i from 0 to n-1.
3) Loop j from i+1 to n-1.
4) If nums[i] == nums[j] and (i * j) % k == 0, increment ans.
5) Return ans.
Complexity Analysis
Time: O(n^2) due to pair enumeration.
Space: O(1) extra space.
Common Pitfalls
- Using i <= j and accidentally counting self-pairs.
- Forgetting the nums[i] == nums[j] condition.
- Checking (nums[i] * nums[j]) % k by mistake (must be indices, not values).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int countPairs(int[] nums, int k) {
int n = nums.length;
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] == nums[j] && (i * j) % k == 0) {
ans++;
}
}
}
return ans;
}
}func countPairs(nums []int, k int) int {
n := len(nums)
ans := 0
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if nums[i] == nums[j] && (i*j)%k == 0 {
ans++
}
}
}
return ans
}class Solution {
public:
int countPairs(vector<int>& nums, int k) {
int n = (int)nums.size();
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] == nums[j] && (i * j) % k == 0) {
++ans;
}
}
}
return ans;
}
};from typing import List
class Solution:
def countPairs(self, nums: List[int], k: int) -> int:
n = len(nums)
ans = 0
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j] and (i * j) % k == 0:
ans += 1
return ansvar countPairs = function(nums, k) {
const n = nums.length;
let ans = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (nums[i] === nums[j] && (i * j) % k === 0) {
ans++;
}
}
}
return ans;
};中文
题目概述
给定整数数组 nums 和整数 k，统计满足以下条件的下标对 (i, j)：i < j、nums[i] == nums[j]、且 (i * j) % k == 0。
核心思路
这题数据范围允许直接枚举所有下标对。每个下标对只需检查两件事：值相等，以及下标乘积能被 k 整除。
暴力解法为何可行
双层循环枚举所有 i < j。若值不等直接跳过；值相等再判断 (i * j) % k == 0。实现简洁，且在本题约束下效率足够。
最优算法步骤
1）初始化答案 ans = 0。
2）外层遍历 i = 0..n-1。
3）内层遍历 j = i+1..n-1。
4）若 nums[i] == nums[j] 且 (i * j) % k == 0，则 ans++。
5）返回 ans。
复杂度分析
时间复杂度：O(n^2)。
空间复杂度：O(1)。
常见陷阱
- 写成 i <= j，把自己和自己配对也算进去了。
- 忘了先判断 nums[i] == nums[j]。
- 误写成 (nums[i] * nums[j]) % k（应当检查下标乘积）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int countPairs(int[] nums, int k) {
int n = nums.length;
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] == nums[j] && (i * j) % k == 0) {
ans++;
}
}
}
return ans;
}
}func countPairs(nums []int, k int) int {
n := len(nums)
ans := 0
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if nums[i] == nums[j] && (i*j)%k == 0 {
ans++
}
}
}
return ans
}class Solution {
public:
int countPairs(vector<int>& nums, int k) {
int n = (int)nums.size();
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] == nums[j] && (i * j) % k == 0) {
++ans;
}
}
}
return ans;
}
};from typing import List
class Solution:
def countPairs(self, nums: List[int], k: int) -> int:
n = len(nums)
ans = 0
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j] and (i * j) % k == 0:
ans += 1
return ansvar countPairs = function(nums, k) {
const n = nums.length;
let ans = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (nums[i] === nums[j] && (i * j) % k === 0) {
ans++;
}
}
}
return ans;
};
Comments