分类： leetcode

目标

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

思路

找出数组中下标不同的数对，使数对元素值相同且下标的乘积能够被 k 整除，返回满足要求的数对个数。

根据题意模拟即可。

有网友提出了使用原数组原地保存后面一个相同元素的下标，组成一个元素值相同的链表，避免重复判断不相等的元素。

也有网友提出了 O(nlogn) 的解法，与当前元素 nums[j] 组成合法数对需要满足 i < j，并且 nums[i] == nums[j] && (i * j) % k == 0。nums[i] 必须提供因子 k2 = k / gcd(k, j)，问题转化为查找 j 前，包含因子 k2 且与当前元素值相同的元素个数。提前预处理每一个数的因子列表，遍历当前值的因子列表，将每一个因子与当前值组成 key 并计数。

代码

/**
 * @date 2025-04-17 0:09
 */
public class CountPairs2176 {

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

性能

目标

给你一个整数数组 arr ，以及 a、b、c 三个整数。请你统计其中好三元组的数量。

如果三元组 (arr[i], arr[j], arr[k]) 满足下列全部条件，则认为它是一个 好三元组 。

• 0 <= i < j < k < arr.length
• |arr[i] - arr[j]| <= a
• |arr[j] - arr[k]| <= b
• |arr[i] - arr[k]| <= c

其中 |x| 表示 x 的绝对值。

返回 好三元组的数量 。

示例 1：

输入：arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
输出：4
解释：一共有 4 个好三元组：[(3,0,1), (3,0,1), (3,1,1), (0,1,1)] 。

示例 2：

输入：arr = [1,1,2,2,3], a = 0, b = 0, c = 1
输出：0
解释：不存在满足所有条件的三元组。

说明：

• 3 <= arr.length <= 100
• 0 <= arr[i] <= 1000
• 0 <= a, b, c <= 1000

思路

返回数组中的好三元组的数量，所谓好三元组就是前两个元素值差的绝对值小于 a，后两个元素元素值差的绝对值小于 b，首尾元素差的绝对值小于 c。

数据量不大可以直接暴力解。

网友提出了另一种解法，枚举 j、k，确定 i 的范围，然后使用前缀和快速获取范围内的元素个数。

代码

/**
 * @date 2025-04-14 0:06
 */
public class CountGoodTriplets1534 {

    public int countGoodTriplets(int[] arr, int a, int b, int c) {
        int n = arr.length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (Math.abs(arr[i] - arr[j]) <= a && Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] - arr[k]) <= c) {
                        res++;
                    }
                }
            }
        }
        return res;
    }
}

性能

目标

给你一个整数数组 nums，你需要确保数组中的元素 互不相同 。为此，你可以执行以下操作任意次：

• 从数组的开头移除 3 个元素。如果数组中元素少于 3 个，则移除所有剩余元素。

注意：空数组也视作为数组元素互不相同。返回使数组元素互不相同所需的 最少操作次数 。

示例 1：

输入： nums = [1,2,3,4,2,3,3,5,7]
输出： 2
解释：
第一次操作：移除前 3 个元素，数组变为 [4, 2, 3, 3, 5, 7]。
第二次操作：再次移除前 3 个元素，数组变为 [3, 5, 7]，此时数组中的元素互不相同。
因此，答案是 2。

示例 2：

输入： nums = [4,5,6,4,4]
输出： 2
解释：
第一次操作：移除前 3 个元素，数组变为 [4, 4]。
第二次操作：移除所有剩余元素，数组变为空。
因此，答案是 2。

示例 3：

输入： nums = [6,7,8,9]
输出： 0
解释：
数组中的元素已经互不相同，因此不需要进行任何操作，答案是 0。

说明：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

思路

每次操作可以删除数组前三个元素，求使数组元素互不相同所需要的最小操作次数。

最直接的想法是记录数组中每个元素的出现次数，同时记录重复元素的个数，然后模拟删除操作，如果将某个元素的出现次数减为 1，那么将重复元素个数减 1，直到重复元素个数为 0，返回操作次数。

网友题解使用逆向思维，倒序遍历数组，直到遇到第一个重复的元素，由于操作是从头开始的，因此一定要删除该重复元素。假如下标是 i，那么需要操作 ⌈(i + 1)/3⌉ = i/3 + 1 次。

对于整数 a >= 0, b > 0，有 ⌈a/b⌉ = ⌊(a + b - 1)/b⌋，将 a = qb + r 带入分析即可。或者直接写 ⌊a/b⌋ + a % b > 0 ? 1 : 0。

正向考虑稍微有点复杂，需要找到重复数字前一个下标中的最大下标。

代码

/**
 * @date 2025-04-08 8:43
 */
public class MinimumOperations3396 {

    public int minimumOperations_v1(int[] nums) {
        int[] index = new int[101];
        Set<Integer> set = new HashSet<>();
        Arrays.fill(index, -1);
        int maxIndex = -1;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (set.contains(num)) {
                maxIndex = Math.max(maxIndex, index[num]);
            }
            set.add(num);
            index[num] = i;
        }
        if (maxIndex == -1) {
            return 0;
        } else {
            return maxIndex / 3 + 1;
        }
    }

    public int minimumOperations(int[] nums) {
        int[] cnt = new int[101];
        Queue<Integer> q = new ArrayDeque<>();
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            q.offer(num);
            if (++cnt[num] > 1) {
                set.add(num);
            }
        }
        if (set.size() == 0) {
            return 0;
        }
        int sameCnt = set.size();
        int res = 0;
        while (!q.isEmpty()) {
            res++;
            for (int i = 0; !q.isEmpty() && i < 3; i++) {
                if (--cnt[q.poll()] == 1) {
                    sameCnt--;
                }
            }
            if (sameCnt == 0) {
                break;
            }
        }
        return res;
    }

}

性能