DSA problem
Continuous Subarray Sum
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 multiple of k is any integer n * k where n is an integer, so 0 is always considered a multiple of k.
The trick is the same congruence idea used to count divisible subarrays: if two prefix sums leave the same remainder modulo k, the subarray between them sums to a multiple of k. To enforce the minimum length of two, we store the earliest index at which each remainder first appeared and only accept a match when the current index is at least two positions later.
Examples
nums = [23,2,4,6,7], k = 6truenums = [23,2,6,4,7], k = 6truenums = [23,2,6,4,7], k = 13falseConstraints
- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^9
- 0 <= sum(nums[i]) <= 2^31 - 1
- 1 <= k <= 2^31 - 1
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.