9.子数组统计问题

子数组计数问题（求个数 \ 长度=>前缀和=>两数之和）

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

• 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
1
2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2
1
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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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]
1
2
3
4
5

示例 2:

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

提示:

• 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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 。
1
2
3

示例 2：

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

示例 3：

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

提示：

• 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

525. 连续数组

中等

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

示例 1:

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

示例 2:

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

提示：

• 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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 。
1
2
3
4
5
6
7
8
9
10
11
12
13

示例 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
2
3
4
5
6
7
8
9
10

提示：

• 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

子串统计类问题（贡献法，思考变化量）

问题：有一个字符串 s，求满足条件的 s 的子串的个数「和」

思考字串统计类问题的通用技巧之一：

贡献法：将所有子串按照其末尾字符的下标分组，考虑两组相邻的字串：以 s[i-1] 结尾的字串、以 s[i] 结尾的字串。

• 以 s[i] 结尾的字串，可以看成以 s[i-1] 结尾的字串，在末尾添加上 s[i] 组成。

那么思考：从左往右遍历s，考虑将 s[i] 添加到以 s[i-1] 结尾的子串的末尾，添加后，以s[i-1]结尾的字串值会如何变化？

相似题目：

• 828. 统计子串中的唯一字符
• 2262. 字符串的总引力 | 题解

828. 统计子串中的唯一字符

困难

我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。

例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。

本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。

注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。

示例 1：

输入: s = "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
     其中，每一个子串都由独特字符构成。
     所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10
1
2
3
4
5

示例 2：

输入: s = "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。
1
2
3

示例 3：

输入：s = "LEETCODE"
输出：92
1
2

提示：

• 1 <= s.length <= 105
• s 只包含大写英文字符

贡献法

https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/solutions/1804144/by-endlesscheng-ko4z/?envType=daily-question&envId=2023-11-26

问题：有一个字符串 s，求满足条件的 s 的子串的个数「和」

思考字串统计类问题的通用技巧之一：

贡献法：将所有子串按照其末尾字符的下标分组，考虑两组相邻的字串：以 s[i-1] 结尾的字串、以 s[i] 结尾的字串。

• 以 s[i] 结尾的字串，可以看成以 s[i-1] 结尾的字串，在末尾添加上 s[i] 组成。

那么思考：从左往右遍历s，考虑将 s[i] 添加到以 s[i-1] 结尾的子串的末尾，添加后，以s[i-1]结尾的字串值会如何变化？

class Solution {
    /**
    我们在从左往右遍历s的同时，对每个字母s[i]
        记录其上一次出现的下标last[s[i]]和上上一次出现的下标last1[s[i]]
    我们可以算出从「以s[i-1]结尾的子串」和「以s[i]结尾的子串」
    countUniqueChars的值，增加/减少了多少
        增加了 i - last0[s[i]] (s[i] 单独作为子串贡献了1)
        减少了 last0[s[i]] - last1[s[i]]
    两者总变化量为 i - 2*last0[s[i]] + last1[s[i]]

    在计算时，如果last0[s[i]]和last1[s[i]]不存在，可以看作-1，保证式子的正确性
       注：i + 2 - 1 ==> i从未出现过，则countUniqueChars的值就会增加i和i自身贡献1
     */
    public int uniqueLetterString(String s) {
        int ans = 0, total = 0; // 这里total就是countUniqueChars
        int[] last0 = new int[26], last1 = new int[26];
        Arrays.fill(last0, -1);
        Arrays.fill(last1, -1);
        for(int i = 0; i < s.length(); i++){
            int c = s.charAt(i) - 'A';
            total += i - 2 * last0[c] + last1[c];
            ans += total;
            last1[c] = last0[c];
            last0[c] = i;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2262. 字符串的总引力【828弱化版】

困难

字符串的 引力 定义为：字符串中 不同 字符的数量。

• 例如，"abbca" 的引力为 3 ，因为其中有 3 个不同字符 'a'、'b' 和 'c' 。

给你一个字符串 s ，返回 其所有子字符串的总引力 。

子字符串 定义为：字符串中的一个连续字符序列。

示例 1：

输入：s = "abbca"
输出：28
解释："abbca" 的子字符串有：
- 长度为 1 的子字符串："a"、"b"、"b"、"c"、"a" 的引力分别为 1、1、1、1、1，总和为 5 。
- 长度为 2 的子字符串："ab"、"bb"、"bc"、"ca" 的引力分别为 2、1、2、2 ，总和为 7 。
- 长度为 3 的子字符串："abb"、"bbc"、"bca" 的引力分别为 2、2、3 ，总和为 7 。
- 长度为 4 的子字符串："abbc"、"bbca" 的引力分别为 3、3 ，总和为 6 。
- 长度为 5 的子字符串："abbca" 的引力为 3 ，总和为 3 。
引力总和为 5 + 7 + 7 + 6 + 3 = 28 。
1
2
3
4
5
6
7
8
9

示例 2：

输入：s = "code"
输出：20
解释："code" 的子字符串有：
- 长度为 1 的子字符串："c"、"o"、"d"、"e" 的引力分别为 1、1、1、1 ，总和为 4 。
- 长度为 2 的子字符串："co"、"od"、"de" 的引力分别为 2、2、2 ，总和为 6 。
- 长度为 3 的子字符串："cod"、"ode" 的引力分别为 3、3 ，总和为 6 。
- 长度为 4 的子字符串："code" 的引力为 4 ，总和为 4 。
引力总和为 4 + 6 + 6 + 4 = 20 。
1
2
3
4
5
6
7
8

提示：

• 1 <= s.length <= 105
• s 由小写英文字母组成

class Solution {
    /**
    考虑将 s[i] 添加到以 s[i-1] 结尾的子串的末尾，添加后，以s[i-1]结尾的字串值会如何变化？

    记录其上一次出现的下标last[s[i]]
    我们可以算出从「以s[i-1]结尾的子串」和「以s[i]结尾的子串」
                tot的值，增加/减少了多少
        增加了 i - last0[s[i]] (s[i] 单独作为子串贡献了1)
     */
    public long appealSum(String s) {
        int[] last0 = new int[27];
        Arrays.fill(last0, -1);
        long res = 0, total = 0;
        for(int i = 0; i < s.length(); i++){
            int c = s.charAt(i) - 'a';
            total += i - last0[c];
            res += total;
            last0[c] = i;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22