Loading...
Loading...
You are given an array of positive integers nums and a positive integer k.
A subarray is a contiguous, non-empty part of nums. Its length is the number of elements in it. A subarray is good if its sum leaves a remainder equal to its length when divided by k, that is, sum % k == length.
Return the number of good subarrays.
Subarrays at different positions are counted separately, even if they hold the same values.
Note that the answer can exceed the 32-bit integer range.
Input: nums = [1,3,2,4], k = 4
Output: 2
Explanation: [1] has sum 1, and 1 % 4 = 1 matches its length 1. [2,4] has sum 6, and 6 % 4 = 2 matches its length 2. No other subarray is good. For example, [3,2] has sum 5 and 5 % 4 = 1, but its length is 2.
Input: nums = [1,4,2,3,5], k = 4
Output: 4
Explanation: The good subarrays are [1] (1 % 4 = 1), [5] (5 % 4 = 1), [4,2] (6 % 4 = 2) and [1,4,2] (7 % 4 = 3).
Input: nums = [4,2,4,2,4,2,4,2], k = 4
Output: 7
Explanation: Every subarray of length 2 has sum 6, and 6 % 4 = 2, so all 7 of them are good. Subarrays of length 1 or 3 leave remainder 0 or 2, so none of them is good. The first four elements have sum 12 and 12 % 4 = 0, which is not 4. The first six elements have sum 18 and 18 % 4 = 2, which is not 6.
Input: nums = [5,5,5], k = 1
Output: 0
Explanation: Every sum leaves remainder 0 when divided by 1, and every length is at least 1.
nums.length ≤2⋅105nums[i] ≤109k ≤109