标签： 前缀和

目标

在第 1 天，有一个人发现了一个秘密。

给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。

给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 10^9 + 7 取余 后返回。

示例 1：

输入：n = 6, delay = 2, forget = 4
输出：5
解释：
第 1 天：假设第一个人叫 A 。（一个人知道秘密）
第 2 天：A 是唯一一个知道秘密的人。（一个人知道秘密）
第 3 天：A 把秘密分享给 B 。（两个人知道秘密）
第 4 天：A 把秘密分享给一个新的人 C 。（三个人知道秘密）
第 5 天：A 忘记了秘密，B 把秘密分享给一个新的人 D 。（三个人知道秘密）
第 6 天：B 把秘密分享给 E，C 把秘密分享给 F 。（五个人知道秘密）

示例 2：

输入：n = 4, delay = 1, forget = 3
输出：6
解释：
第 1 天：第一个知道秘密的人为 A 。（一个人知道秘密）
第 2 天：A 把秘密分享给 B 。（两个人知道秘密）
第 3 天：A 和 B 把秘密分享给 2 个新的人 C 和 D 。（四个人知道秘密）
第 4 天：A 忘记了秘密，B、C、D 分别分享给 3 个新的人。（六个人知道秘密）

说明：

• 2 <= n <= 1000
• 1 <= delay < forget <= n

思路

在第 1 天有一个人发现了一个秘密，每一个新知道秘密的人在 delay 天之后的 每一天 会向一个 新人 分享这个秘密，每一个人在知道秘密之后的 forget 天会忘记秘密，求第 n 天结束时知道秘密的人数。

定义 dp[i] 表示在第 i 天 新增 知道秘密的人数，它等于超过了延迟 delay 并且还没有忘记的人数总和，也即 [i - forget + 1, i - delay] 之间的新增人数总和，求和可以使用前缀和优化。

代码

/**
 * @date 2025-09-09 8:57
 */
public class PeopleAwareOfSecret2327 {

    public int peopleAwareOfSecret(int n, int delay, int forget) {
        int[] dp = new int[n + 1];
        int mod = 1000000007;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = Math.max(0, i - forget + 1); j <= Math.max(0, i - delay); j++) {
                dp[i] = (dp[i] + dp[j]) % mod;
            }
        }
        int res = 0;
        for (int i = Math.max(0, n - forget + 1); i <= n; i++) {
            res = (res + dp[i]) % mod;
        }
        return res;
    }

}

性能

目标

给你一个正整数 n ，你需要找到一个下标从 0 开始的数组 powers ，它包含 最少 数目的 2 的幂，且它们的和为 n 。powers 数组是 非递减 顺序的。根据前面描述，构造 powers 数组的方法是唯一的。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti] ，其中 queries[i] 表示请你求出满足 lefti <= j <= righti 的所有 powers[j] 的乘积。

请你返回一个数组 answers ，长度与 queries 的长度相同，其中 answers[i]是第 i 个查询的答案。由于查询的结果可能非常大，请你将每个 answers[i] 都对 10^9 + 7 取余 。

示例 1：

输入：n = 15, queries = [[0,1],[2,2],[0,3]]
输出：[2,4,64]
解释：
对于 n = 15 ，得到 powers = [1,2,4,8] 。没法得到元素数目更少的数组。
第 1 个查询的答案：powers[0] * powers[1] = 1 * 2 = 2 。
第 2 个查询的答案：powers[2] = 4 。
第 3 个查询的答案：powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64 。
每个答案对 10^9 + 7 得到的结果都相同，所以返回 [2,4,64] 。

示例 2：

输入：n = 2, queries = [[0,0]]
输出：[2]
解释：
对于 n = 2, powers = [2] 。
唯一一个查询的答案是 powers[0] = 2 。答案对 10^9 + 7 取余后结果相同，所以返回 [2] 。

说明：

• 1 <= n <= 10^9
• 1 <= queries.length <= 10^5
• 0 <= starti <= endi < powers.length

思路

给定一个正整数，将其拆分成最少数目的 2 的幂，即二进制表示中每一个 1 所表示的 2 的幂，按照从小到大的顺序放入 nums。有一个查询数组 queries，queries[i] = [from, to] 表示查询 nums 从 from 到 to 的乘积，返回对应的结果数组。

由于 nums 长度最大 31，因此可以提前预处理所有子数组的乘积，或值直接暴力计算查询范围内的元素乘积。

注意不能计算前缀乘积，为了防止溢出存的是余数，相除后取余并不满足分配律。或者换一种思路计算幂次的前缀和，然后再计算 2 的幂对 mod 取余。

代码

/**
 * @date 2025-08-11 9:52
 */
public class ProductQueries2438 {

    public int[] productQueries(int n, int[][] queries) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 31; i++) {
            int p = 1 << i;
            if ((n & p) == p) {
                list.add(p);
            }
        }
        int mod = 1000000007;
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int from = queries[i][0];
            int to = queries[i][1];
            res[i] = 1;
            for (int j = from; j <= to; j++) {
                res[i] = (int) ((long) res[i] * list.get(j) % mod);
            }
        }
        return res;
    }

}

性能

目标

给你一个下标从 0 开始的整数数组 nums ，以及整数 modulo 和整数 k 。

请你找出并统计数组中 趣味子数组 的数目。

如果 子数组 nums[l..r] 满足下述条件，则称其为 趣味子数组 ：

• 在范围 [l, r] 内，设 cnt 为满足 nums[i] % modulo == k 的索引 i 的数量。并且 cnt % modulo == k 。

以整数形式表示并返回趣味子数组的数目。

注意：子数组是数组中的一个连续非空的元素序列。

示例 1：

输入：nums = [3,2,4], modulo = 2, k = 1
输出：3
解释：在这个示例中，趣味子数组分别是： 
子数组 nums[0..0] ，也就是 [3] 。 
- 在范围 [0, 0] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。
- 因此 cnt = 1 ，且 cnt % modulo == k 。
子数组 nums[0..1] ，也就是 [3,2] 。
- 在范围 [0, 1] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。
- 因此 cnt = 1 ，且 cnt % modulo == k 。
子数组 nums[0..2] ，也就是 [3,2,4] 。
- 在范围 [0, 2] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。
- 因此 cnt = 1 ，且 cnt % modulo == k 。
可以证明不存在其他趣味子数组。因此，答案为 3 。

示例 2：

输入：nums = [3,1,9,6], modulo = 3, k = 0
输出：2
解释：在这个示例中，趣味子数组分别是： 
子数组 nums[0..3] ，也就是 [3,1,9,6] 。
- 在范围 [0, 3] 内，只存在 3 个下标 i = 0, 2, 3 满足 nums[i] % modulo == k 。
- 因此 cnt = 3 ，且 cnt % modulo == k 。
子数组 nums[1..1] ，也就是 [1] 。
- 在范围 [1, 1] 内，不存在下标满足 nums[i] % modulo == k 。
- 因此 cnt = 0 ，且 cnt % modulo == k 。
可以证明不存在其他趣味子数组，因此答案为 2 。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= modulo <= 10^9
• 0 <= k < modulo

思路

统计数组的趣味子数组数目，趣味子数组指模 modulo 余 k 的元素个数模 modulo 也余 k。

关键点是如何将左右下标解耦。

代码

/**
 * @date 2025-04-25 0:35
 */
public class CountInterestingSubarrays2845 {

    public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
        long res = 0L;
        int n = nums.size();
        int[] prefix = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + (nums.get(i - 1) % modulo == k ? 1 : 0);
        }
        long[] cnt = new long[Math.min(modulo, n + 1)];
        for (int right = 0; right <= n; right++) {
            if (prefix[right] - k >= 0) {
                res += cnt[(prefix[right] - k) % modulo];
            }
            cnt[prefix[right] % modulo]++;
        }
        return res;
    }

}

性能

目标

给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：

• 选择两个满足 0 <= i, j < nums.length 的不同下标 i 和 j 。
• 选择一个非负整数 k ，满足 nums[i] 和 nums[j] 在二进制下的第 k 位（下标编号从 0 开始）是 1 。
• 将 nums[i] 和 nums[j] 都减去 2^k 。

如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为 0 的数组，那么我们称它是一个 美丽 的子数组。

请你返回数组 nums 中 美丽子数组 的数目。

子数组是一个数组中一段连续 非空 的元素序列。

示例 1：

输入：nums = [4,3,1,2,4]
输出：2
解释：nums 中有 2 个美丽子数组：[3,1,2] 和 [4,3,1,2,4] 。
- 按照下述步骤，我们可以将子数组 [3,1,2] 中所有元素变成 0 ：
  - 选择 [3, 1, 2] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [1, 1, 0] 。
  - 选择 [1, 1, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 0, 0] 。
- 按照下述步骤，我们可以将子数组 [4,3,1,2,4] 中所有元素变成 0 ：
  - 选择 [4, 3, 1, 2, 4] 和 k = 2 。将 2 个数字都减去 22 ，子数组变成 [0, 3, 1, 2, 0] 。
  - 选择 [0, 3, 1, 2, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 2, 0, 2, 0] 。
  - 选择 [0, 2, 0, 2, 0] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [0, 0, 0, 0, 0] 。

示例 2：

输入：nums = [1,10,4]
输出：0
解释：nums 中没有任何美丽子数组。

说明：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^6

思路

有一个下标从 0 开始的数组 nums，每次操作可以任选两个不同下标的元素，如果它们在二进制下的第 k 位是 1，那么将这两个元素减去 2^k，即把这两个元素的第 k 位置 0。如果对 nums 的子数组执行任意次操作后可以将子数组所有元素变为 0，称该子数组为 美丽子数组。返回数组 nums 的美丽子数组数目。

通过分析可以知道，累加美丽子数组中所有元素在二进制下每个bit位上 1 的个数，可以发现每个位置上 1 的个数都是偶数。可以通过异或运算来判断是否是美丽子数组。

代码

/**
 * @date 2025-03-06 8:37
 */
public class BeautifulSubarrays2588 {

    public long beautifulSubarrays(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        Map<Integer, List<Integer>> map = new HashMap<>();
        map.computeIfAbsent(prefix[0], x -> new ArrayList<>()).add(0);
        for (int i = 1; i <= n; i++) {
            prefix[i] = nums[i - 1] ^ prefix[i - 1];
            map.computeIfAbsent(prefix[i], x -> new ArrayList<>()).add(i);
        }
        long res = 0;
        for (List<Integer> value : map.values()) {
            int size = value.size();
            res += (size - 1L) * size / 2;
        }
        return res;
    }

}

性能

目标

给你一个下标从 0 开始长度为 n 的整数数组 nums 。

如果以下描述为真，那么 nums 在下标 i 处有一个 合法的分割 ：

• 前 i + 1 个元素的和 大于等于 剩下的 n - i - 1 个元素的和。
• 下标 i 的右边 至少有一个 元素，也就是说下标 i 满足 0 <= i < n - 1 。

请你返回 nums 中的 合法分割 方案数。

示例 1：

输入：nums = [10,4,-8,7]
输出：2
解释：
总共有 3 种不同的方案可以将 nums 分割成两个非空的部分：
- 在下标 0 处分割 nums 。那么第一部分为 [10] ，和为 10 。第二部分为 [4,-8,7] ，和为 3 。因为 10 >= 3 ，所以 i = 0 是一个合法的分割。
- 在下标 1 处分割 nums 。那么第一部分为 [10,4] ，和为 14 。第二部分为 [-8,7] ，和为 -1 。因为 14 >= -1 ，所以 i = 1 是一个合法的分割。
- 在下标 2 处分割 nums 。那么第一部分为 [10,4,-8] ，和为 6 。第二部分为 [7] ，和为 7 。因为 6 < 7 ，所以 i = 2 不是一个合法的分割。
所以 nums 中总共合法分割方案受为 2 。

示例 2：

输入：nums = [2,3,1,0]
输出：2
解释：
总共有 2 种 nums 的合法分割：
- 在下标 1 处分割 nums 。那么第一部分为 [2,3] ，和为 5 。第二部分为 [1,0] ，和为 1 。因为 5 >= 1 ，所以 i = 1 是一个合法的分割。
- 在下标 2 处分割 nums 。那么第一部分为 [2,3,1] ，和为 6 。第二部分为 [0] ，和为 0 。因为 6 >= 0 ，所以 i = 2 是一个合法的分割。

说明：

• 2 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5

思路

求数组的合法分割点个数，下标 i 是合法分割点的条件是 前 i + 1 个元素和大于剩余元素和，且至少要有一个元素。

直接的想法是计算前缀和，然后按照题意计算。

实际实现时发现只用到了 所有元素的和 sum 以及区间 [0, i] 的和 tmp，无需存储前缀，直接在遍历的时候计算就可以。

代码

/**
 * @date 2025-01-13 8:41
 */
public class WaysToSplitArray2270 {

    public int waysToSplitArray(int[] nums) {
        long sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int res = 0;
        long tmp = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            tmp += nums[i];
            if (2 * tmp >= sum) {
                res++;
            }
        }
        return res;
    }

}

性能