可被整除的三元组数量
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
在算法中,如何保证左侧和右侧的余数统计在更新过程中不会互相干扰?
▷🦆
为什么每次循环更新右侧余数统计时只减去当前元素`x % d`的值,而不是对所有可能的余数值进行调整?
▷🦆
算法在计算`d - (x % d + k) % d) % d`时的目的是什么?请解释这个表达式如何帮助找到符合条件的三元组。
▷