問題背景

給你一個下標從 $0$ 開始長度為 $n$ 的整數數組 $nums$ 和一個整數 $k$，請你返回滿足 $0\le i<j<n$，$nums[i]=nums[j]$ 且 $(i\times j)$ 能被 $k$ 整除的數對 $(i,j)$ 的 數目 。

數據約束

• $1\le nums.length\le 100$
• $1\le nums[i],k\le 100$

解題過程

這題數據范圍不大，暴力枚舉也能過。
一種更好的做法，是將值像等的元素都保存在鏈表中，遍歷時就只需要判斷能否整除了。

具體實現

class Solution {public int countPairs(int[] nums, int k) {int n = nums.length;int res = 0;ListNode[] map = new ListNode[110];for (int i = 0; i < n; i++) {ListNode cur = new ListNode(i);ListNode pre = map[nums[i]];if (pre != null) {cur.next = pre;}while (pre != null) {if (i * pre.index % k == 0) {res++;}pre = pre.next;}map[nums[i]] = cur;}return res;}
}class ListNode {int index;ListNode next;ListNode(int index) {this.index = index;next = null;}
}