Problem Statement

Given an array and a sum k, we need to print the length of the longest subarray that sums to k.

Examples

Example 1:

Input: array[] = {1, 3, 4, 7, 9 }, k(sum) = 7
Output: 2
Explanation: The longest subarray with sum 7 is {3, 4}

Different Approaches

Using Two Pointers

Code

#include <iostream>
#include <vector>

using namespace std;

int longestSubarrayWithSumK(const vector<int>& nums, int K) {
    int left = 0;
    int right = 0;
    int currentSum = 0;
    int maxLength = 0;

    while (right < nums.size()) {
        // Add current element to currentSum
        currentSum += nums[right];

        // Shrink the window if the sum exceeds K
        while (currentSum > K) {
            currentSum -= nums[left];
            left++;
        }

        // Update maxLength if applicable
        maxLength = max(maxLength, right - left + 1);

        // Move right pointer to the next element
        right++;
    }

    return maxLength;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    int K = 9;
    cout << "Length of longest subarray with sum " << K << ": " << longestSubarrayWithSumK(nums, K) << endl;
    return 0;
}


// Output

Length of longest subarray with sum 9: 3

Complexity Analysis

Time Complexity:O(2 * N), where N = size of the given array.

• The outer while loop i.e the right pointer can move up to index (n -1). Now, the inner while loop i.e., the left pointer can move up to the right pointer at most. So, every time the inner loop does not run for n times rather it can run for n times in total. So, the time complexity will be O(2*N) instead of O(N^2).

Space Complexity:O(1)