Continuous Subarray Sum
Problem 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
xis a multiple ofkif there exists an integernsuch thatx = n * k.0is always a multiple ofk.
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
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The brute force approach involves considering all subarrays and calculating their sum to see if it's a multiple of k. We can iterate over each start index, then from that start index, iterate through possible end indices, maintaining the sum of the subarray and checking it against k.
Code:
- Time Complexity: O(n^2) due to the nested loops checking all subarrays.
- Space Complexity: O(1) as only a few integer variables are used.
2. Prefix Sum with Modulo HashMap
Intuition:
Instead of checking every subarray, use a hashmap to store the remainder of the prefix sum when divided by k. If the same remainder appears again (and the subarray length between these points is greater than 1), it indicates a subarray sum which is a multiple of k.
Code:
- Time Complexity: O(n) as we only traversed the array once.
- Space Complexity: O(min(n, k)) due to the map storing at most
kdifferent mod values. In scenarios where many duplicates exist, the space can potentially approachn.