題目資訊

• 題目編號: 2176
• 題目連結: Count Equal and Divisible Pairs in an Array
• 主題: Array

題目敘述

給定一個從0開始索引的整數陣列 nums，其長度為 $n$，以及一個整數 $k$，返回滿足條件的數對 $(i, j)$ 的數量，其中 $0 \leq i < j < n$，使得 $\text{nums}[i] == \text{nums}[j]$ 且 $(i \times j)$ 可以被 $k$ 整除。

範例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
說明：由於 nums 中沒有重複的值，因此沒有數對 (i, j) 能滿足所有條件。

約束條件：

• $1 \leq \text{nums.length} \leq 100$
• $1 \leq \text{nums}[i], k \leq 100$

直覺

此問題要求在陣列中找到索引對 $(i, j)$，使得在這些索引處的值相等，且指數乘積 $i \times j$ 可被給定的整數 $k$ 整除。由於給定的約束條件暗示了一個暴力法可能是可行的。最簡單的方法就是遍歷所有可能的索引對，檢查條件，並計數那些滿足所有條件的對。這種方法直截了當，特別是在考慮到問題的約束要求對等性和可整除性核查時。

解法

此演算法使用巢狀迴圈來探索每一個可能的索引對 $(i, j)$，其中 $i < j$。以下是分步說明：

1. 初始化：首先將計數器 count 初始化為零。此計數器將累計滿足問題所需條件的有效對的數量。

2. 外層迴圈：從索引 i = 0 開始，迭代至 $n - 2$，其中 $n$ 是陣列 nums 的長度。外層迴圈的作用是固定潛在對的第一個元素。

3. 內層迴圈：對於每一個固定的索引 i，從索引 j = i + 1 至 $n - 1$ 進行迭代。此內層迴圈將固定的元素 nums[i] 與所有後續的元素 nums[j] 配對，確保 $i < j$。

4. 條件檢查：

   • 等同性檢查：確定當前索引對的元素是否相等，即 nums[i] == nums[j]。
   • 整除性檢查：檢查指數乘積 $i \times j$ 是否能被 $k$ 整除，即 $(i \times j) % k == 0$。

5. 計數：如果某個特定對 $(i, j)$ 滿足兩個條件，則將 count 加一。

6. 結果：當所有對都經過檢查後，返回 count 作為符合條件的有效對的總數。

由於巢狀迴圈遍歷所有對，此方法的時間複雜度為 $O(n^2)$。考慮到限制相對較小（$n$ 最多為 100），此方法在提供的限制範圍內運行效率良好。直接檢查每對所需的條件，保證演算法正確識別所有有效的對。

程式碼

C++

class Solution {
public:
    int countPairs(vector<int>& nums, int k) {
        int count = 0; // 初始化計算配對的計數器

        // 遍歷每個元素並尋找配對
        for (int i = 0; i < nums.size() - 1; i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                // 檢查當前的配對 (i, j) 是否符合條件
                if (i * j % k == 0 && nums[i] == nums[j]) {
                    count++; // 若條件滿足則遞增計數器
                }
            }
        }

        return count; // 返回符合條件的配對總數
    }
};

Python

class Solution:
    def countPairs(self, nums, k):
        count = 0  # 初始化計數器以計算配對數量

        # 尋找每個元素並找出配對
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                # 檢查當前配對 (i, j) 是否符合條件
                if i * j % k == 0 and nums[i] == nums[j]:
                    count += 1  # 如果條件滿足，計數器加一

        return count  # 返回滿足條件的有效配對總數

複雜度分析

• 時間複雜度: 給定演算法的時間複雜度是 $O(n^2)$。這是因為存在兩個嵌套的迴圈: 外層迴圈遍歷 nums 的元素，從索引 $0$ 到 $n-2$，內層迴圈則從索引 $i+1$ 到 $n-1$ 遍歷。因此，總的迭代次數是前 $n-1$ 個整數之和，即 $\frac{(n-1)n}{2}$，在大 O 表示法中簡化為 $O(n^2)$。

• 空間複雜度: 演算法的空間複雜度是 $O(1)$。演算法使用固定數量的額外空間，即單一整數 count 來存儲有效配對的數量。輸入列表 nums 和整數 $k$ 作為輸入參數被給予，因此不計入演算法本身的空間複雜度。