Easy

题目描述

给你一个下标从 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

解题思路

这道题要求我们找到满足两个条件的数对：

  1. nums[i] == nums[j]
  2. (i * j) % k == 0

由于数组长度最大为100，我们可以使用暴力枚举的方法来解决。

解法思路：

  1. 使用双层循环枚举所有可能的数对 (i, j)，其中 i < j
  2. 对于每个数对，检查是否满足以下条件：
    • nums[i] == nums[j]（值相等）
    • (i * j) % k == 0（下标乘积能被k整除）
  3. 统计满足条件的数对数量

这种暴力解法在给定的数据规模下是完全可行的，时间复杂度为 O(n²)，对于 n ≤ 100 来说非常高效。

另一种优化思路是先按值分组，然后在每组内部检查下标乘积的整除性，但在这个数据规模下，简单的暴力枚举已经足够且更容易理解。

代码实现

class Solution {
public:
    int countPairs(vector<int>& nums, int k) {
        int count = 0;
        int n = nums.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j] && (i * j) % k == 0) {
                    count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        count = 0
        n = len(nums)
        
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] == nums[j] and (i * j) % k == 0:
                    count += 1
        
        return count

public class Solution {
    public int CountPairs(int[] nums, int k) {
        int count = 0;
        int n = nums.Length;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j] && (i * j) % k == 0) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countPairs = function(nums, k) {
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] === nums[j] && (i * j) % k === 0) {
                count++;
            }
        }
    }
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)双层循环遍历所有数对
空间复杂度O(1)只使用常数额外空间

相关题目