LeetCode - 和可被K整除的子数组

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

题目描述：一个连续的区间可以被k整除。

一个连续的区间可以被k整除，如果用前缀和就是(arr[r] - arr[l - 1]) / k = 0;当然，在计算机语言里面，用除法判断结果是否为0不行，需要用%,(arr[r] - arr[l - 1]) % k = 0，其实可以转化一下，arr[r] % k = arr[l - 1] % k，也就是说，在前缀和数组中，找到等于arr[l - 1] % k的数字出现的个数即可。如何知道某个数字出现的个数？使用哈希，哈希可以完成此操作。

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> record;
        record[0] = 1; // 对哈希初始化，防止nums数组中存在以本身为符合条件的数字
        int sum = 0;
        int ans = 0;
        for (auto &t : nums)
        {
            sum += t;
            int mod = (sum % k + k) % k; // C++中，负数的余数还是负数，需要进行处理，转变为正数
            if (record.count(mod)) 
            {
                ans += record[mod]; 
            }
            ++record[mod];
        }
        return ans;
    }
};