290 ms super simple java solution


  • 9
    K
    public class Solution {
        
        public int minSubArrayLen(int targetSum, int[] nums) {
            int minLength = Integer.MAX_VALUE;
            
            int left=0, right=0;
            int slidingSum = 0;
            int n = nums.length;
            
            while(right < n) {
                if(slidingSum  + nums[right] < targetSum) {
                    slidingSum += nums[right];
                    right += 1;
                } else {
                    minLength = Math.min(minLength, right - left + 1);
                    slidingSum -= nums[left];
                    left += 1;
                }
            }
            
            return minLength == Integer.MAX_VALUE ? 0 : minLength;
        }
    }

  • 1
    S

    This is an amazing solution. It is fast as it is an O(n) solution and it is quite elegant as well. I walked through step by step the algorithm and I believe that I understand how it works. However, how did you think of this clever solution?

    With 2 indicies, you divided the problem into 2 cases:

    1. If the sum from Left to Right < s: You would increment Right.
    2. If the sum from Left to Right >= s: Store the minimum of current min_length and the length between left and right, increment Left and thus decreasing the sum.

    I have been looking at this question, but I just didn't find something so clever. How did you think of this?


  • 0
    N

    One minor improvement to the code above, if found minLength == 1, meaning a value in the array is >= targetSum, return immediately.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.