C++ Simple O(n) solution


  • 39
    J
    class Solution {
    public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int firstPos = 0, sum = 0, minLength = INT_MAX;
        for(int i = 0; i<nums.size(); i++) {
            sum += nums[i];
            while(sum >= s) {
                minLength = min(minLength, i - firstPos + 1);
                sum -= nums[firstPos++];
            }
        }
        
        return minLength == INT_MAX? 0 : minLength;
      }
    };

  • -2
    P
    I hava a similar solution
    public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int length=nums.length;
        int minlength=Integer.MAX_VALUE,sublength=0;
        int sum=0;
        for(int i=0;i<length;)
        {
          while(sum<s&&i<length)
             { 
               sum+=nums[i++];
               sublength++;
             }
        
           
             while(sum>=s)
              {
                minlength=Math.min(minlength,sublength);  
                sum-=nums[i-sublength];  
                sublength--;
                
              }
             
    
              
        }
        
        return minlength<Integer.MAX_VALUE?minlength:0;
    }
    

    }


  • -1
    I

    Hi,
    How about the case s = 5, nums = new [] int { 9 };

    in this case , I think correct answer is 0, but it return 1


  • 1
    J

    It is correct. We need to find the minimal length of a subarray of which the sum ≥ s. The list, nums, you gave me is 9 (which is sum) is bigger than 5, so it should return 1.


  • 0
    I

    Thanks for your clarification


  • 0
    Z

    while O(n)??


  • 0
    J

    This is because while loops at most N times during looping for-loop from 1 to N. So, N + N = O(N).


  • 0
    M

    It is very useful.


  • 0
    C
    This post is deleted!

  • 0

    Good O(n) solution!


  • 0
    F

    good answer.


  • 0
    N

    very concise solution


  • 0
    L

    How it is O(n)?


Log in to reply
 

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