523. Continuous Subarray Sum

Description

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 <= 105
• 0 <= nums[i] <= 109
• 0 <= sum(nums[i]) <= 231 - 1
• 1 <= k <= 231 - 1

Solutions

Solution 1: Prefix Sum + Hash Table

According to the problem description, if there exist two positions \(i\) and \(j\) (\(j < i\)) where the remainders of the prefix sums modulo \(k\) are the same, then the sum of the subarray \(\textit{nums}[j+1..i]\) is a multiple of \(k\).

Therefore, we can use a hash table to store the first occurrence of each remainder of the prefix sum modulo \(k\). Initially, we store a key-value pair \((0, -1)\) in the hash table, indicating that the remainder \(0\) of the prefix sum \(0\) appears at position \(-1\).

As we iterate through the array, we calculate the current prefix sum's remainder modulo \(k\). If the current prefix sum's remainder modulo \(k\) has not appeared in the hash table, we store the current prefix sum's remainder modulo \(k\) and its corresponding position in the hash table. Otherwise, if the current prefix sum's remainder modulo \(k\) has already appeared in the hash table at position \(j\), then we have found a subarray \(\textit{nums}[j+1..i]\) that meets the conditions, and thus return \(\textit{True}\).

After completing the iteration, if no subarray meeting the conditions is found, we return \(\textit{False}\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\).

Python3JavaC++GoTypeScript

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        d = {0: -1}
        s = 0
        for i, x in enumerate(nums):
            s = (s + x) % k
            if s not in d:
                d[s] = i
            elif i - d[s] > 1:
                return True
        return False

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer, Integer> d = new HashMap<>();
        d.put(0, -1);
        int s = 0;
        for (int i = 0; i < nums.length; ++i) {
            s = (s + nums[i]) % k;
            if (!d.containsKey(s)) {
                d.put(s, i);
            } else if (i - d.get(s) > 1) {
                return true;
            }
        }
        return false;
    }
}

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> d{{0, -1}};
        int s = 0;
        for (int i = 0; i < nums.size(); ++i) {
            s = (s + nums[i]) % k;
            if (!d.contains(s)) {
                d[s] = i;
            } else if (i - d[s] > 1) {
                return true;
            }
        }
        return false;
    }
};

func checkSubarraySum(nums []int, k int) bool {
    d := map[int]int{0: -1}
    s := 0
    for i, x := range nums {
        s = (s + x) % k
        if _, ok := d[s]; !ok {
            d[s] = i
        } else if i-d[s] > 1 {
            return true
        }
    }
    return false
}

function checkSubarraySum(nums: number[], k: number): boolean {
    const d: Record<number, number> = { 0: -1 };
    let s = 0;
    for (let i = 0; i < nums.length; ++i) {
        s = (s + nums[i]) % k;
        if (!d.hasOwnProperty(s)) {
            d[s] = i;
        } else if (i - d[s] > 1) {
            return true;
        }
    }
    return false;
}

Comments