每日算法-250603
每日算法学习
今天学习了两道关于子数组和的 LeetCode 题目。
1524. 和为奇数的子数组数目
题目
思路 💡
前缀和
核心思想：子数组
arr[i..j]的和可以表示为两个前缀和之差，即prefixSum[j+1] - prefixSum[i](假设prefixSum[k]表示arr[0...k-1]的和，且prefixSum[0] = 0)。我们希望这个差为奇数。根据奇偶性运算规则：
- 奇数 - 偶数 = 奇数
- 偶数 - 奇数 = 奇数
这意味着，如果当前的前缀和
P_current是奇数，我们需要查找在它之前出现过的偶数前缀和的个数。反之，如果P_current是偶数，我们需要查找之前出现过的奇数前缀和的个数。
解题过程 ⚙️
- 计算前缀和数组
prefix。prefix[k]存储原数组arr从索引0到k-1的元素之和。特别地，prefix[0]通常设为0，代表空数组的和。- 遍历计算出的每一个前缀和
x(从prefix[0]开始)：
- 我们用一个 Map
map来存储已遍历过的前缀和中，奇数和偶数各自出现的次数。在代码中，map的键true代表奇数前缀和的计数，false代表偶数前缀和的计数。- 对于当前前缀和
x：
- 如果
x是 奇数：我们需要找到一个之前的偶数前缀和P_prev_even，使得x - P_prev_even为奇数。此时，结果ret加上map中记录的偶数前缀和的个数。- 如果
x是 偶数：我们需要找到一个之前的奇数前缀和P_prev_odd，使得x - P_prev_odd为奇数。此时，结果ret加上map中记录的奇数前缀和的个数。- 更新
map：将当前前缀和x的奇偶性对应的计数加 1。- 初始状态：
prefix[0] = 0是一个偶数。所以在遍历开始前（或者说，在处理prefix[0]时），偶数前缀和的计数为 1，奇数前缀和的计数为 0。代码中通过先查询后更新的方式，巧妙地处理了这一点：当处理prefix[0]=0(偶数)时，它会查询奇数前缀和的个数（初始为0，所以ret不变），然后将偶数前缀和的个数更新为1。
复杂度 📈
- 时间复杂度: O ( N ) O(N) O(N)，其中 N 是数组
arr的长度。计算前缀和需要 O ( N ) O(N) O(N)，遍历前缀和数组也需要 O ( N ) O(N) O(N)。 - 空间复杂度: O ( N ) O(N) O(N)，主要用于存储前缀和数组
prefix。map的空间是 O ( 1 ) O(1) O(1)，因为它只存储两个键值对。
Code
class Solution {public int numOfSubarrays(int[] arr) {long ret = 0;int n = arr.length;final int MOD = 1_000_000_007;int[] prefix = new int[n + 1];Map<Boolean, Integer> map = new HashMap<>(n + 1); // true - 奇数 false - 偶数for (int i = 0; i < n; i++) {prefix[i + 1] = prefix[i] + arr[i];}for (int x : prefix) {// key 为奇数就去找偶数有多少个 key为偶数就去找奇数有多少个boolean key = (x % 2 == 0);ret = (ret + map.getOrDefault(key, 0)) % MOD;// 存进map时注意取反map.put(!key, map.getOrDefault(!key, 0) + 1);}return (int) ret;}
}
974. 和可被 K 整除的子数组
题目
思路 💡
前缀和 + 同余定理
核心思想：子数组
nums[i..j]的和为S = prefixSum[j+1] - prefixSum[i]。
我们希望S能被K整除，即S % K == 0。根据同余定理，如果
(A - B) % K == 0，那么A % K == B % K。应用到这里：
(prefixSum[j+1] - prefixSum[i]) % K == 0等价于prefixSum[j+1] % K == prefixSum[i] % K。因此，我们只需要统计具有相同余数的前缀和出现的次数。
注意处理负数取模：在 Java (以及很多语言)中，负数对正数取模的结果可能是负数 (例如
-1 % 5 = -1)。为了确保余数始终在[0, K-1]区间内，我们通常使用(sum % K + K) % K。
解题过程 ⚙️
- 初始化一个变量
prefixSum = 0(表示当前累积的前缀和) 和结果ret = 0。- 使用一个数组
map来存储每个前缀和模K的余数出现的次数。map[rem]表示余数rem已经出现了多少次。- 关键初始化：
map[0] = 1。这非常重要！它代表在开始遍历数组之前，我们有一个“空前缀和”（值为0），其模K的余数是0。这能够正确处理那些从数组第一个元素开始其和就能被K整除的子数组。- 遍历数组
nums中的每个元素num:
a. 更新prefixSum += num。
b. 计算当前prefixSum模K的余数：remainder = (prefixSum % K + K) % K。
c. 在map中查找这个remainder之前已经出现过的次数，计为count = map[remainder]。这意味着有count个之前的某个前缀和P_prev满足P_prev % K == remainder。对于每一个这样的P_prev，子数组(P_current - P_prev)都能被K整除。所以，将count加到ret上：ret += count。
d. 然后，将当前prefixSum的余数remainder计入map：map[remainder]++。
复杂度 📈
- 时间复杂度: O ( N ) O(N) O(N)，其中 N 是数组
nums的长度。我们只遍历数组一次。 - 空间复杂度: O ( K ) O(K) O(K)，
map数组的大小固定为K，用于存储余数的计数。
Code
class Solution {public int subarraysDivByK(int[] nums, int k) {int ret = 0, prefix = 0;int[] map = new int[k];map[0] = 1; // prefix[i] % k = 0的情况for (int num : nums) {prefix += num;ret += map[(prefix % k + k) % k]++;}return ret;}
}