前缀和算法实战：和为 K 的子数组与和可被 K 整除的子数组

Java 实现

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0, 1);
        
        int sum = 0, ret = 0;
        for (int x : nums) {
            sum += x;
            
            // 统计结果，getOrDefault 避免空指针
            ret += hash.getOrDefault(sum - k, 0);
            
            // 把当前的前缀和丢到哈希表里面
            hash.put(sum, hash.getOrDefault(sum, 0) + 1);
        }
        return ret;
    }
}

复杂度分析： 时间复杂度 O(n)，空间复杂度 O(n)。

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

题目描述： 给定一个整数数组 A，返回其中元素之和可被 K 整除的非空连续子数组的数目。

解法一：暴力枚举

枚举所有子数组并求和判断，时间复杂度 O(n³) 或 O(n²)，数据量大时会超时，这里不再赘述。

解法二：前缀和 + 同余定理

补充知识：负数取模

在 C++ 中，负数取模的结果可能为负。例如 -1 % 3 = -1。但在数学同余理论中，我们希望余数是正数。修正公式为 (a % n + n) % n，这样可以保证结果始终在 [0, n-1] 范围内。

核心思路

根据同余定理：如果 (a - b) % k == 0，那么 a % k == b % k。

对于子数组 [x, i]，其和为 sum[i] - sum[x-1]。若该和能被 k 整除，则 sum[i] % k == sum[x-1] % k。

因此，问题转化为：在遍历过程中，记录每个前缀和余数出现的次数。当计算到当前位置的余数 r 时，查看之前有多少次出现过相同的余数 r，这些位置都可以作为合法的起点。

代码实现

C++ 实现

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        // 处理细节：余数为 0 的情况初始化为 1
        hash[0] = 1;
        
        int sum = 0, ret = 0;
        for (auto x : nums) {
            sum += x;
            
            // 求出修正后的余数，确保为正
            int r = (sum % k + k) % k;
            
            if (hash.count(r)) {
                ret += hash[r];
            }
            
            hash[r]++;
        }
        return ret;
    }
};

Java 实现

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0, 1);
        
        int sum = 0, ret = 0;
        for (int x : nums) {
            sum += x;
            
            // 计算当前位置的前缀和余数
            int r = (sum % k + k) % k;
            
            ret += hash.getOrDefault(r, 0);
            hash.put(r, hash.getOrDefault(r, 0) + 1);
        }
        return ret;
    }
};

复杂度分析： 时间复杂度 O(n)，空间复杂度 O(min(n, k))。

总结

这两个问题都利用了前缀和的思想，将区间和问题转化为单点查询问题。关键在于理解 sum[i] - sum[j] 的关系，以及如何利用哈希表高效存储历史信息。特别是第二个问题中的负数取模处理，是面试中的常见陷阱，务必掌握。