974. 和可被 K 整除的子数组
本文共 1231 字，大约阅读时间需要 4 分钟。
解决方案是利用前缀和和哈希表来记录余数，从而在O(n)时间内找到满足条件的子数组数目。
思路：
问题分析： 寻找所有满足条件的连续子数组，其和可被给定的整数K整除。这类似于在寻找特定子数组，但和中的余数问题可以通过前缀和处理。
前缀和： 使用前缀和数组可以简化子数组和的问题。考虑前缀和sum[i] = A[0] + A[1] + ... + A[i]。任意子数组sum[j+1..i]的和等于前缀和sum[i] - sum[j]。
哈希表记录余数： 每次更新前缀和sum，计算sum % K的值。使用哈希表记录当前余数次数，可以快速判断是否存在差值k的倍数的子数组。即，相同的余数表示它们的差值是k的倍数。
处理负数： 对于负数部分，直接在计算余数时使用模运算的正确方式，确保余数为非负数。
实现步骤：
初始化前缀和sum为0，结果res为0，哈希表记录余数出现次数。
遍历数组，更新前缀和sum，并计算当前余数r。若r在哈希表中存在，说明之前有相同的余数，构成满足条件的子数组，因此res增加对应的计数。
将当前余数r的计数更新到哈希表中。
处理特殊情况，如K等于0。
代码：
#include #include using namespace std;class Solution {public: int subarraysDivByK(vector &A, int K) { if (K == 0) return 0; // 处理K=0的情况 long long sum = 0; int res = 0; unordered_map r_map; r_map[0] = 1; // 初始余数0出现一次 for (int num : A) { sum += num; int r = sum % K; if (r < 0) r += K; // 确保余数为正 res += r_map[r]; r_map[r]++; } return res; }};
解释：
初始化： 前缀和sum初始值为0，结果res初始化为0。哈希表r_map记录余数及其出现次数，从而非常快速地查询余数是否存在。
遍历数组： 对于每个元素，更新前缀和sum。计算余数r，处理负数余数为正数。
更新结果： 当余数r存在于哈希表时，说明存在满足条件的子数组，结果res加上此时的余数次数。然后更新哈希表中的余数次数。
返回结果： 经过整个遍历，返回满足条件的子数组数目。
这种方法在O(n)时间复杂度内完成，高效地解决了问题。
转载地址：http://nmcuk.baihongyu.com/