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^42 <= 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;
}