Longest Subarray With Sum K

Problem Statement

Find longest subarray Length having k Sum

Intuition

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

https://www.codingninjas.com/studio/problems/longest-subarray-with-sum-k_5713505?utm_source=striver&utm_medium=website&utm_campaign=a_zcoursetuf&leftPanelTabValue=PROBLEM

Video Links

https://www.youtube.com/watch?v=frf7qxiN2qU&ab_channel=takeUforward

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;
}

Approach 3:

C++

Approach 4:

C++

Similar Problems