Longest Subarray With Sum X
Given an array of N integers A and a target sum X, find the length of the longest contiguous subarray of A whose elements sum up to exactly X. If no such subarray exists, output 0.
Input
The first line contains two integers N and X, where N is the size of the array and X is the target sum. The second line contains N integers, the elements of the array A.
Output
Print a single integer: the length of the longest subarray summing to X. Output 0 if no such subarray exists.
Constraints
1 <= N <= 200000 -10^9 <= A[i] <= 10^9 -10^{14} <= X <= 10^{14}
Example 1
5 7 2 4 -1 1 3
4
The subarray [4, -1, 1, 3] sums to 7 and has length 4. The subarray [2, 4, -1] sums to 5. The subarray [4, -1, 1] sums to 4. The subarray [-1, 1, 3] sums to 3. The subarray [2, 4] sums to 6. The subarray [4, -1] sums to 3. The subarray [-1, 1] sums to 0. The subarray [1, 3] sums to 4. The subarray [
Example 2
3 5 1 2 3
2
No subarray sums to 5. The subarray [2, 3] sums to 5, length 2. [1, 2, 3] sums to 6. [1, 2] sums to 3. The longest is length 2.
Hints
Similar problems
- Longest Subarray with Equal HalvesMedium
- Count Subarrays with Target SumEasy
- Count Subarrays with Distinct ElementsMedium
- Longest Subarray with Sum at Most KMedium
- Longest Subarray with At Most K Distinct ElementsMedium
- Longest Substring With At Most K Distinct CharactersMedium
More topics: Hash Map and Hashing problems, Sliding Window problems, Prefix Sums problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 7 2 4 -1 1 3
3 5 1 2 3