974.Subarray Sums Divisible by K

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

題目描述

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⁴
-10⁴ <= nums[i] <= 10⁴
2 <= k <= 10⁴

解答

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>
Yen-Chi ChenThu, Jan 19, 2023

思路:

若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會出現的次數

做法:

做prefix sum 及 %k掃一遍, 累計%k值出現的次數為答案

Time: $O (n)$
Extra Space: $O (k)$

XD 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 理解力薄弱ＱＱ

玉山

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給大家笑
Marsgoat Feb 13, 2023

Reference

回到題目列表