子数组计数问题

子数组计数（区间）问题通常和【前缀和】有关，将区间和化为pre[r] - pre[l] = xx ，式子变换，转变成 pre[l] = xxx的形式， 然后问题化为对pre数组的两数之和问题

参考：https://blog.csdn.net/csdn_edition/article/details/117068924

• Java负数取余：(a+b) % k, b<0 ==> ((a + b) % k + k) % k

题单

1. 求个数

• 560. 和为 K 的子数组
• 974. 和可被 K 整除的子数组

2. 求长度（最大长度就维护哈希表第一个出现的值first,求最短长度就维护最后一个出现的值last。）

• 523. 连续的子数组和
• 525. 连续数组

Problem: 面试题 17.05. 字母与数字 【first】

Problem: 1590. 使数组和能被 P 整除 【比较难，last】

Problem: 1171. 从链表中删去总和值为零的连续节点 【last】

560. 和为 K 的子数组

中等

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

class Solution {
    /**
    1. 如何快速统计子数组和为k ==> 前缀和
        区间[left, right]的和 = k
        ==> pre[right+1] - pre[left] = k
        式子变换 pre[right+1] - k = pre[left]
        用哈希表记录pre[l]出现的次数  => 两数之和
     */
    public int subarraySum(int[] nums, int k) {
        int ans = 0, n = nums.length;
        int[] pre = new int[n+1];
        for(int i = 0; i < n; i++)
            pre[i+1] = pre[i] + nums[i];
        Map<Integer, Integer> map = new HashMap<>();
        for(int right : pre){
            int left = right - k;
            if(map.containsKey(left)) ans += map.get(left);
            map.merge(right, 1, Integer::sum);
        }
        return ans;
    }
}

974. 和可被 K 整除的子数组

中等

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空） 子数组 的数目。

子数组 是数组的 连续 部分。

示例 1：

输入：nums = [4,5,0,-2,-3,1], k = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 k = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

示例 2:

输入: nums = [5], k = 9
输出: 0

提示:

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• 2 <= k <= 104

class Solution {
    /**
    元素之和可被 k 整除的（连续、非空） 子数组
     (pre[r] - pre[l]) % k = 0 
     ==> pre[r] % k = pre[l] % k
     */
    public int subarraysDivByK(int[] nums, int k) {
        int n = nums.length, ans = 0;
        int[] pre = new int[n+1];
        for(int i = 0; i < n; i++) // java负数取余
            pre[i+1] = ((pre[i] + nums[i])%k + k) % k;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // 如果前缀和为0，pre[i] 可以被任意数整数
        for(int i = 1; i <= n; i++){
            int left = pre[i];
            if(map.containsKey(left)) ans += map.get(left);
            map.merge(left, 1, Integer::sum);
        }
        return ans;
    }
}

523. 连续的子数组和

中等

给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：

• 子数组大小 至少为 2 ，且
• 子数组元素总和为 k 的倍数。

如果存在，返回 true ；否则，返回 false 。

如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。

示例 1：

输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。

示例 2：

输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。 
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。

示例 3：

输入：nums = [23,2,6,4,7], k = 13
输出：false

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= sum(nums[i]) <= 231 - 1
• 1 <= k <= 231 - 1

class Solution {
    // [i, j]
    // sum[j] - sum[i] = n*k
    // sum[j] / k - sum[i] / k = n
    // ==> sum[j] / k == sum[i] / k
    public boolean checkSubarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] pre = new int[n+1];
        for(int i = 0; i < n; i++)
            pre[i+1] = pre[i] + nums[i];
        Set<Integer> set = new HashSet<>();
        // 子数组长度至少为2，从2开始枚举右端点
        for(int i = 2; i <= n; i++){
            set.add(pre[i-2] % k);
            int left = pre[i] % k;
            if(set.contains(left))
                return true;
        }
        return false;
    }
}

525. 连续数组

中等

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

提示：

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1

class Solution {
    // 要求一段连续数组0和1的数量相同 ==>
    // (s[r] - s[l]) * 2 = R - L
    // ==> s[r] * 2 - R = s[l] * 2 - l
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int presum = 0;
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>(); // s[pos]*2-pos, pos
        map.put(1, -1);
        for(int i = 0; i < n; i++){
            presum += nums[i];
            if(map.containsKey(presum*2-i))
                res = Math.max(res, i - map.get(presum*2-i));
            else
                map.put(presum*2 - i, i);
        }
        return res;
    }
}

2845. 统计趣味子数组的数目

中等

给你一个下标从 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 <= 105
• 1 <= nums[i] <= 109
• 1 <= modulo <= 109
• 0 <= k < modulo

https://leetcode.cn/problems/count-of-interesting-subarrays/solutions/2424063/qian-zhui-he-ha-xi-biao-fu-ti-dan-by-end-74bb/

class Solution {
    /**
    1. 转换 设 cnt 为满足 nums[i] % m == k 的索引 i 的数量
        如果 nums[i] % m == k，则 nums[i] = 1，否则 nums[i] = 0
        ==> cnt = 子数组的元素和   ==> 前缀和

    2. 取模 cnt % modulo == k  ==> (pre[r] - pre[l]) % m = k
                               ==> (pre[r] % m - pre[l] % m + m) % m = k
    3. 式子变形 (pre[r] % m - pre[l] % m + m) % m = k
                (pre[r] - k + m) % m = pre[l]
        用哈希表记录pre[l]出现的次数  => 两数之和
     */
    public long countInterestingSubarrays(List<Integer> nums, int m, int k) {
        int n = nums.size();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++)
            arr[i] = (nums.get(i) % m == k) ? 1 : 0;
        int[] pre = new int[n+1];
        for(int i = 0; i < n; i++)
            pre[i+1] = pre[i] + arr[i];

        Map<Integer, Integer> map = new HashMap<>();
        long res = 0;
        for(int num : pre){
            int left = (num - k + m) % m;
            res += map.getOrDefault(left, 0);
            map.merge(num%m, 1, Integer::sum);
        }
        return res;
    }
}

其他

拼多多笔试题.多多的求和计算

多多路上从左到右有N棵树（编号1～N），其中第i个颗树有和谐值Ai。

多多鸡认为，如果一段连续的树，它们的和谐值之和可以被M整除，那么这个区间整体看起来就是和谐的。

现在多多鸡想请你帮忙计算一下，满足和谐条件的区间的数量。

输入描述：

• 第一行，有2个整数N和M，表示树的数量以及计算和谐值的参数。

• （ 1 <= N <= 100,000, 1 <= M <= 100 ）

• 第二行，有N个整数Ai, 分别表示第i个颗树的和谐值。

• （ 0 <= Ai <= 1,000,000,000 ）

/**
	(pre[r] - pre[l]) % m = 0
	pre[l] = pre[r]%m
*/