974. Subarray Sums Divisible by K

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: 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^4
  • -10^4 <= nums[i] <= 10^4
  • 2 <= k <= 10^4

二、分析

  • 觀察此題，要求子序列的和可以被 k 整除，我們可以用 prefix sum 來做這一題，那麼就可以利用 prefix[j] - prefix[j] 來檢查是否被 k 整除，若可以整除代表從 i+1 到 j 的子序列，為符合題意的子序列。
  • 為了方便起見，要檢查 0 到 j 是否滿足，那麼 i 需要為 -1，故我們可以預先將 0 加入 prefix array 中，代表，到 j 為止沒有跳過任一元素。
  • 由於我們要查找兩數相減可以被 k整除，我們可以預先將 prefix sum 處理成範為在 0~k 之間的數，那麼我們需要查找的，便是 prefix[i] == prefix[j]，證明：
    • \(0<a<k,0<b<k\)
    • \(-k<b-a<k\)
    • \(在 -k與 k之間，只有 0 滿足 k 的倍數，也就是a=b\)
  • 根據上述關係，我們可以利用 Hash Table，更高效的查找我們需要的找的對象，而不必真的存一個 prefix array。

三、解題

1. prefix sum

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)
int subarraysDivByK(vector<int>& nums, int k) {
    // vector<int> prefix = {0};
    int sum = 0;
    int res = 0;
    unordered_map<int,int> map;
    map[0] = 1;
    for (const auto& x : nums) {
        sum += x;
        int val = sum % k;
        if (val < 0) val += k;
        // prefix.push_back(val);
        if (map.count(val)) res += map[val];
        map[val]++;
    }
    return res;
}

回目錄 Catalog