Sliding Window - Longest - Two Pointers / Sliding Window

Problems
1

https://algo.monster/problems/subarray_sum_longest

2

In the template code, should we do inside the while loop: ans = max(ans, window) ? since the window is invalid there…

3

Please add more test cases, it’s really hard to know whether solutions that differ to yours actually catch the edge cases properly, or even whether your code does in practice

5 
public static int subarraySumLongest(List<Integer> nums, int target) {
        LinkedList<Integer> list = new LinkedList<>();
        int sum = 0;
        int prev = 0;
        int result = 0;
        for (int i = 0; i < nums.size(); i++){
           int current = nums.get(i);

           if (current + sum <= target){
               result = Math.max(result, list.size());
           } else {
               sum -= nums.get(prev);
               list.removeFirst();
               prev++;
           }
            sum+= current;
        }
        return result;
    }```
7

So its going to be O(n^2) ?
can we make it On(n)

8

I don’t think it is O(n^2) because that would mean there exists an array of inputs that will cause the inner while loop to execute n times for every iteration of the for loop. That cannot be possible because start index will never exceed the end index.

The only case where the inner while loop will execute O(n) times is when the end index reaches the last value and only the last value makes sum > target, but the while loop will only iterate n-1 times for that last iteration of the for loop.

ex: target = 20 nums=[1, 2, 3, 4, 20]
sum = 1 + 2 + 3 + 4 = 10 (at no iteration so far has the while loop executed because sum <= target
then
sum = 10 + 20 = 30 (then the while loop runs n-1 times to move start forward)