【Leetcode 每日一题】2176. 统计数组中相等且可以被整除的数对
问题背景
给你一个下标从 0 0 0 开始长度为 n n n 的整数数组 n u m s nums nums 和一个整数 k k k，请你返回满足 0 ≤ i < j < n 0 \le i < j < n 0≤i<j<n， n u m s [ i ] = n u m s [ j ] nums[i] = nums[j] nums[i]=nums[j] 且 ( i × j ) (i \times j) (i×j) 能被 k k k 整除的数对 ( i , j ) (i, j) (i,j) 的 数目 。
数据约束
- 1 ≤ n u m s . l e n g t h ≤ 100 1 \le nums.length \le 100 1≤nums.length≤100
- 1 ≤ n u m s [ i ] , k ≤ 100 1 \le nums[i], k \le 100 1≤nums[i],k≤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;}
}