Approach 1: (Pos + Neg)
Map + Hashing
Intuition is
1 2 3 6
Prefix 1 3 6 12
| |
At each stage I check for sum-k
Meaning 12-6 is Required sum=6
Hence We know that subarray has sum = 6
We hash the sum at each step , But not hashing the same sum again,
Might lead to shorter sum if we update
Approach 2: For Pos only
Sliding window for sum = k
```cpp
/*
Problem is When sum increases we decrease the window,
But the problem is that sum can be decreased later by some negative value later
We are not counting that
eg->
-1 0 1 1) -1
As we reach high here we decrease the window, but see that
if we want k = 0
*/
```
Links
Video Links
Approach 1:
C++
#include <bits/stdc++.h>
int getLongestSubarray(vector<int>& nums, int k){
// sum-> index
unordered_map<int,int> mp;
int sum = 0;
int ans = 0;
for(int i=0; i<nums.size(); i++){
sum += nums[i];
if(sum == k)
ans = max(ans, i+1);
if(mp.find(sum - k) != mp.end())
ans = max(ans, i-mp[sum-k]);
if(mp.find(sum) == mp.end())
mp[sum] = i;
}
return ans;
}
Approach 2:
Sliding Window
C++
#include <bits/stdc++.h>
int longestSubarrayWithSumK(vector<int> nums, long long k) {
int ans = 0;
long long sum = 0;
for(int low=0, high=0; high<nums.size(); high++){
sum += nums[high];
while(sum > k){
sum -= nums[low++];
}
if(sum == k){
ans = max(ans, high-low+1);
}
}
return ans;
}