# 974. Subarray Sums Divisible by K
###### tags: `LeetCode`
## **Link**
https://leetcode.com/problems/subarray-sums-divisible-by-k/

## **Code**

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
        int n=nums.size(),ans=0;
        vector<int> sum(n,0),ct(k,0); // sum存前綴和，ct計算前綴和對k取餘數的數量
        sum[0]=nums[0]%k; // 頭的前綴和就是自己
        if(sum[0]>=0) // 判斷前綴和正負=>負數取餘數後還是負數，要加k
            ++ct[sum[0]];
        else
            ++ct[sum[0]+k];
        for(int i=1;i<n;++i) // 建好sum和ct
        {
            sum[i]=(sum[i-1]+nums[i])%k; // 前綴和是前一個的前綴和加上自己
            if(sum[i]>=0) // 一樣判斷正負
                ++ct[sum[i]];
            else
                ++ct[sum[i]+k];
        }
        ans+=ct[0]; // 最一開始，取餘數為0就是我們要的，所以把ans加上ct[0]
        for(int i=1;i<n;++i) // 開始砍頭
        {                    // 如果A%k=m且B%k=m，則(A-B)%k=0
            if(sum[i-1]>=0) // 判斷正負，並扣掉前一個sum在ct裡的數量
                ans+=--ct[sum[i-1]];
            else
                ans+=--ct[sum[i-1]+k];
        }
        return ans;
    }
};

## date
**2023.01.19**

{%hackmd @nnks8908/background_leetcode %}