问题背景
给你一个下标从 0 0 0 开始的整数数组 n u m s nums nums，以及整数 m o d u l o modulo modulo 和整数 k k k。
请你找出并统计数组中 趣味子数组 的数目。
如果 子数组 n u m s [ l . . r ] nums[l..r] nums[l..r] 满足下述条件，则称其为 趣味子数组 ：
- 在范围 [ l , r ] [l, r] [l,r] 内，设 c n t cnt cnt 为满足 n u m s [ i ] nums[i] % modulo == k nums[i] 的索引 i i i 的数量。并且 c n t cnt % modulo = k cnt。
以整数形式表示并返回趣味子数组的数目。
注意：子数组是数组中的一个连续非空的元素序列。
数据约束
- 1 ≤ n u m s . l e n g t h ≤ 1 0 5 1 \le nums.length \le 10 ^ 5 1≤nums.length≤105
- 1 ≤ n u m s [ i ] ≤ 1 0 9 1 \le nums[i] \le 10 ^ 9 1≤nums[i]≤109
- 1 ≤ m o d u l o ≤ 1 0 9 1 \le modulo \le 10 ^ 9 1≤modulo≤109
- 0 ≤ k < m o d u l o 0 \le k < modulo 0≤k<modulo
解题过程
首先做一个转化，数组中的元素其实可以分为两类，划分的标准是是否满足 n u m s [ i ] m o d m o d u l o = k nums[i] \ mod \ modulo = k nums[i] mod modulo=k。
如果将满足上述条件的元素用 1 1 1 来表示，不满足的用 0 0 0 来表示，那么符合条件的元素数目就等价于子数组的元素和，元素和可以通过前缀和方便地计算出来。
在前缀和数组 p r e S u m preSum preSum 中，要求 ( p r e S u m [ r i g h t ] − p r e S u m [ l e f t ] ) m o d m o d u l o = k (preSum[right] - preSum[left]) \ mod \ modulo = k (preSum[right]−preSum[left]) mod modulo=k，也即 ( p r e S u m [ r i g h t ] − p r e S u m [ l e f t ] ) m o d m o d u l o = k m o d m o d u l o (preSum[right] - preSum[left]) \ mod \ modulo = k \ mod \ modulo (preSum[right]−preSum[left]) mod modulo=k mod modulo， p r e S u m [ r i g h t ] − p r e S u m [ l e f t ] preSum[right] - preSum[left] preSum[right]−preSum[left] 和 k k k 关于模 m o d u l o modulo modulo 同余， ( p r e S u m [ r i g h t ] − k ) m o d m o d u l o = p r e S u m [ l e f t ] m o d m o d u l o (preSum[right] - k) \ mod \ modulo = preSum[left] \ mod \ modulo (preSum[right]−k) mod modulo=preSum[left] mod modulo。
这样一来，只要用哈希表统计 p r e S u m [ l e f t ] m o d m o d u l o preSum[left] \ mod \ modulo preSum[left] mod modulo，再枚举右端点累计答案即可。
具体实现
class Solution {public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {int n = nums.size();int[] preSum = new int[n + 1];for (int i = 0; i < n; i++) {preSum[i + 1] = preSum[i] + (nums.get(i) % modulo == k ? 1 : 0);}int[] count = new int[Math.min(n + 1, modulo)];long res = 0;for (int item : preSum) {if (item >= k) {res += count[(item - k) % modulo];}count[item % modulo]++;}return res;}
}