leetcode
leetcode 2551 ~ 2600
可被整除的三元组数量

可被整除的三元组数量

难度:

标签:

题目描述

代码结果

运行时间: 147 ms, 内存: 16.3 MB


/*
 * 思路:
 * 1. 使用Java Stream遍历数组中的所有可能的三元组。
 * 2. 过滤出和可以被目标值整除的三元组。
 * 3. 计数所有符合条件的三元组。
 */

import java.util.stream.IntStream;

public class DivisibleTripletsStream {
    public long countDivisibleTriplets(int[] nums, int target) {
        return IntStream.range(0, nums.length - 2)
                .boxed()
                .flatMap(i -> IntStream.range(i + 1, nums.length - 1)
                        .boxed()
                        .flatMap(j -> IntStream.range(j + 1, nums.length)
                                .filter(k -> (nums[i] + nums[j] + nums[k]) % target == 0)
                                .mapToObj(k -> new int[]{i, j, k})))
                .count();
    }
}

解释

方法:

题解采用了一种余数法来找出数组中能被整数d整除的三元组数量。该方法的核心思想是将问题转化为两个前缀和后缀的余数统计问题。对于数组中的每个元素x,固定x为三元组的中间元素,并统计在x左侧和右侧出现的余数的频率。通过这种方式,可以快速计算出以x为中心,符合条件的三元组数量。具体来说,对于每个x,通过查看左侧余数为k的数量和右侧余数为(d-(x%d+k)%d)%d的数量,通过相乘即可得到以x为中心的符合条件的三元组个数。

时间复杂度:

O(n*d)

空间复杂度:

O(d)

代码细节讲解

🦆
在算法中,如何保证左侧和右侧的余数统计在更新过程中不会互相干扰?
在算法实现中,为了避免左侧和右侧余数统计相互干扰,我们分别维护了两个字典`s1`和`s2`来记录左侧和右侧的余数频率。在遍历数组的过程中,我们先更新右侧余数统计(即在处理当前元素`x`之前从`s2`中减去`x % d`的计数),然后处理当前元素,最后更新左侧余数统计(即在处理下一个元素之前将当前元素加入`s1`)。这种处理方式确保在计算以当前元素为中心的三元组时,左右两侧的数据是独立且准确的。
🦆
为什么每次循环更新右侧余数统计时只减去当前元素`x % d`的值,而不是对所有可能的余数值进行调整?
每次循环在处理一个元素`x`时,只需要将这个元素从右侧余数统计`s2`中减去,因为只有这个元素即将被考虑到左侧或者被固定为中心元素。这种方式可以有效减少不必要的操作,因为只有当前元素`x`从右侧转移到左侧或者作为中心元素时,右侧的统计数据才需要更新。其他余数值没有变化,因此不需要调整。
🦆
算法在计算`d - (x % d + k) % d) % d`时的目的是什么?请解释这个表达式如何帮助找到符合条件的三元组。
这个表达式用于计算右侧需要的特定余数,以确保整个三元组的和能够被`d`整除。具体来说,`x % d`是中心元素`x`的余数,`k`是左侧余数。根据整除的性质,三个数的和被`d`整除的条件是这三个数的余数和也应该被`d`整除。因此,表达式`d - (x % d + k) % d) % d`计算的是,给定左侧的余数`k`和中心的余数`x % d`后,右侧的数需要满足的余数条件。这样,只要右侧的余数频率中存在符合这个计算结果的余数,就可以与左侧的`k`和中心的`x`组成符合条件的三元组。

相关问题