LeetCode - 523. Continuous Subarray Sum

Medium

寫完這題去寫 974. Subarray Sums Divisible by K 吧！思路很像，可以來個 double kill

974. Subarray Sums Divisible by K

題目

Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.

A good subarray is a subarray where:

its length is at least two, and
the sum of the elements of the subarray is a multiple of k.

Note that:

A subarray is a contiguous part of the array.
An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

Example 1:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

Example 2:

Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.

Example 3:

Input: nums = [23,2,6,4,7], k = 13
Output: false

Constraints:

1 <= nums.length <=
0 <= nums[i] <=
0 <= sum(nums[i]) <= - 1
1 <= k <= - 1

解題思路

用前綴和的餘數，可以推出哪個區間之內的和可以被整除

利用 prefixSum % k 的餘數，如果有別格與他相減 == 0 且這兩格之間不只差 1，就可以確定這區間和是 k 的倍數

思路公式如下:
prefix[j] = Q1 * k + R1, prefix[i] = Q2 * k + R2

((Q1 - Q2) * k + (R1 - R2)) % k == 0

prefix[j] % k == prefix[i] % k

Solution Code

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        if(nums.size() < 2) return false;

        unordered_map<int, int> modSeen;
        int prefixSum[nums.size()+5];

        modSeen[0] = 0;
        prefixSum[0] = 0;

        for(int i = 1; i <= nums.size(); ++i){
            prefixSum[i] = prefixSum[i-1] + nums[i-1];

            // 存 prefixSum % k 餘數，如果有別格與他相減 == 0 且這兩格之間不只差 1，就可以確定這區間和是 k 的倍數
            // prefix[j] = Q1 * k + R1, prefix[i] = Q2 * k + R2
            // ((Q1 - Q2) * k + (R1 - R2)) % k == 0
            // prefix[j] % k == prefix[i] % k 
            prefixSum[i] %= k;

            if(modSeen.find(prefixSum[i]) != modSeen.end()){
                if(i - modSeen[prefixSum[i]] > 1) return true;
            }
            else modSeen[prefixSum[i]] = i;
        }
        
        return false;
    }
};