974.Subarray Sums Divisible by K
===

###### tags: `Medium`,`Array`,`Hash Table`,`Prefix Sum`

[974. Subarray Sums Divisible by K](https://leetcode.com/problems/subarray-sums-divisible-by-k/)

### 題目描述

Given an integer array `nums` and an integer `k`, return *the number of non-empty **subarrays** that have a sum divisible by* `k`.

A **subarray** is a **contiguous** part of an array.

### 範例

**Example 1:**

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

**Example 2:**

Input: nums = [5], k = 9
Output: 0

**Constraints**:

* 1 <= `nums.length` <= 3 * 10^4^
* -10^4^ <= `nums[i]` <= 10^4^
* 2 <= `k` <= 10^4^

### 解答
#### C++

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        vector<int> sums(k, 0);
        sums[0]++;
        int sum = 0, ans = 0;
        for (auto n : nums) {
            sum = (sum + n % k + k) % k;
            ans += sums[sum];
            sums[sum]++;
        }
        return ans;
    }
};

> `sums`可以用`unordered_map<int, int>`來取代`vector<int>`
> [name=Yen-Chi Chen][time=Thu, Jan 19, 2023]

##### 思路:
1. 若subarray合法, 即`nums[i:j]`可被`k`整除, 利用prefix sum表示為`(sum[j]-sum[i-1] % k) == 0`, 或者是說`sum[j]-sum[i-1] == k * n`, 左右`%k`化簡後變`sum[j]%k == sum[i-1]%k`, 故`sum[j]%k`出現的次數, 即為array以`j`為結束的index時, 合法array會出現的次數

##### 做法:
1. 做`prefix sum` 及 `%k`掃一遍, 累計`%k`值出現的次數為答案

Time: $O(n)$
Extra Space: $O(k)$
> [name=XD] [time= Jan 19, 2023]

#### Python

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        #若 sum[j]%k == sum[i]%k 則ans+=1
        #  4 9 9 7 4 5
        #0 4 4 4 2 4 0 prefix sum％k
        # 四個4 C(4,2) + 兩個0 C(2,2) = 8 + 1 = 9

        acc_n = [0]
        buf = 0
        for n in nums:
            buf += n 
            acc_n.append( buf%k )
        
        stat = dict()
        for n in acc_n:
            if n in stat:
                stat[n] += 1
            else:
                stat[n] = 1
        import math
        ans = 0
        #print(stat)
        for k,v in stat.items():
            ans += int( v*(v-1)/2 )
        return ans
            

寫完了才看懂樓上的code XDD 理解力薄弱ＱＱ
> [name=玉山]

#### Javascript

function subarraysDivByK(nums, k) {
  const map = new Array(k).fill(0);
  let sum = 0;
  let count = 0;
  map[0] = 1;

  for (const num of nums) {
    sum += num;
    const mod = ((sum % k) + k) % k;
    count += map[mod];
    map[mod]++;
  }

  return count;
}

> 本來寫得太醜了，參考吉神的答案，醜陋版跟TLE版本放在Discord給大家笑
> [name=Marsgoat] [time= Feb 13, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)