307. Longest Stretch Adding to K
Challenge1000 ms256 MBSolved by 0%
Print the length of the longest contiguous stretch summing to exactly k.
Print 0 if there is none.
Values may be negative, which rules out a sliding window: growing the window does not reliably increase the sum, so there is no rule for when to shrink it.
Prefix sums handle it. A stretch ending at i sums to k exactly when some
earlier prefix equals current - k, so keep a map from prefix sum to the
EARLIEST index at which it occurred and the longest such stretch falls out.
Earliest is the operative word. Recording a later index would still find a valid stretch, just a shorter one.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000` - `-1000000000000000 ≤ k ≤ 1000000000000000`
Input
The first line contains two integers n and k.
The second line contains n integers.
Output
Print one integer, the length of the longest stretch summing to k, or 0.
Input7 3
1 2 3 1 1 1 1
Output3
Notehas a longer stretch of small values beating a shorter exact one
Input3 6
1 2 3
Output3
Noteis the whole array, which needs the seeded empty prefix
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution