Practice › Sliding Window
Longest Subarray with Sum K
Medium · Sliding Window · Asked at Amazon, Microsoft, TCS, Infosys
All numbers are positive. Find the length of the longest contiguous subarray whose sum is exactly k, or 0 if none exists.
Input
First line: n. Second line: n integers. Third line: k.
Output
The maximum length, or 0.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ a[i] ≤ 10^4
- 1 ≤ k ≤ 10^9
Example 1
Input
7 1 2 3 1 1 1 1 3
Output
3
Example 2
Input
2 5 6 4
Output
0
Hints
- With only positive numbers, a window whose sum is too big can only be fixed by shrinking it from the left.
- Expand right, shrink left while sum > k, and record the length whenever the sum equals k.
Approach
Sliding window: add a[r] to the sum, and while the sum exceeds k remove a[l] and move l forward. If the sum is now exactly k, update the best length with r − l + 1. This works only because all values are positive. With negatives you'd need the prefix-sum + hash-map method instead.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
long long k, sum = 0;
cin >> k;
int best = 0, l = 0;
for (int r = 0; r < n; r++) {
sum += a[r];
while (sum > k) sum -= a[l++];
if (sum == k) best = max(best, r - l + 1);
}
cout << best << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a, k = data[1 : n + 1], data[n + 1]
best = total = l = 0
for r in range(n):
total += a[r]
while total > k:
total -= a[l]
l += 1
if total == k:
best = max(best, r - l + 1)
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
long k = sc.nextLong(), sum = 0;
int best = 0, l = 0;
for (int r = 0; r < n; r++) {
sum += a[r];
while (sum > k) sum -= a[l++];
if (sum == k) best = Math.max(best, r - l + 1);
}
System.out.println(best);
}
}Solve Longest Subarray with Sum K online · All practice problems