LeetCode 2176. Count Equal and Divisible Pairs in an Array 題解

LeetCode 2176. Count Equal and Divisible Pairs in an Array 是一道簡單的陣列相關題目，根據其輸入值的範圍，可以直接考慮遍歷陣列並枚舉滿足條件的目標值進行求解。

在本站的碼不停題系列文章中，筆者會採「一題一解」的方式，並且只提供 Java 程式語言版本的程式範例，其他程式語言的範例程式以及不同解法，則會放置於這個站點上。

題意理解

給定一個長度為 n 的整數陣列 nums，以及整數 k。要求返回滿足以下條件的有序數對 (i, j) 的數量：

對應陣列元素相同：\( \texttt{nums[i]} = \texttt{nums[j]} \)
索引乘積為 k 的倍數：\( (i \times j) \mod{} k = 0 \)

由於陣列 nums 的長度不大，採用 \( \mathcal{O} (n^2) \) 的解法即可；除此之外陣列 nums 中的元素也不大，不需要考慮溢出問題。

解法：遍歷枚舉

思路想法

直觀的操作就是使用嵌套的兩層循環，遍歷陣列枚舉所有數對 (i, j) 並檢查是否滿足題目要求的條件。

範例程式

class Solution {
    public int countPairs(int[] nums, int k) {
        int n = nums.length;
        
        int ans = 0;
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if ((i * j) % k == 0 && nums[i] == nums[j]) {
                    ans += 1;
                }
            }
        }

        return ans;
    }
}

實現時需要注意循環的範圍：

由於要尋找的是滿足條件的有序索引 數對（pairs） 而不是任意兩個元素的組合，恆有 \( 0 \leq i < j \) 的事實，內層循環設置 j = i + 1 可以避免重複計算。
當索引值 i = n - 1 時，內層循環的索引值 j = i + 1 = n 會超出陣列有效索引範圍。