Getting confused why the loop invariant should be while(tail <= nums.length) rather than tail < nums.length


  • 0
    D

    Here's my solution.
    public class Solution {
    /*
    * @param

    */
    
    public int minSubArrayLen(int s, int[] nums) {
        //Remember! The first part should be check whether the array is null.
        if(nums == null || nums.length == 1)
            return 0;
            
        int sum = 0;
        int result = nums.length;
        int head = 0; //Two pointers.
        int tail = 0;
        boolean exists = false;
        while(tail <= nums.length){
            if(sum >= s){
                exists = true;
                if(tail - head == 1)
                    return 1;
                result = Math.min(result, tail - head);
                sum = sum - nums[head];
                head++;
            }else{
                if(tail == nums.length){
                    break;
                }
                sum += nums[tail];
                tail++;
            }
            
        }
        if(exists)
            return result;
        else
            return 0;
    }
    

    }


  • 0
    M

    It's just the way you have coded. Nothing wrong with the code. But, a few things I would like to point out.
    Let's say we have and array [2,3,4,5] and the sum should be 5.
    When your tail points to 4, you are considering numbers 2,3 only. So when the value of tail is nums.length you are considering numbers till nums.length-1.
    In order to avoid this scenario, I would suggest that you do tail-head+1 for calculation, as arrays are 0 based indeces. This change will result in changing a bit of the other parts of the code as well. Here is my code for reference.

    public class Solution {
        public int minSubArrayLen(int s, int[] nums) {
            if(nums==null || nums.length==0){
                return 0;
            }
            int sum=nums[0], start=0, end=0,count=Integer.MAX_VALUE;
            while(end<nums.length && start<=end){
                if(sum>=s){
                    if(count>(end-start+1)){
                        count=end-start+1;
                    }
                    sum-=nums[start];
                    start++;
                }else if(sum<s){
                    end++;
                    if(end<nums.length){
                        sum+=nums[end];    
                    }else{
                        break;
                    }
                    
                }
                
            }
            if(count==Integer.MAX_VALUE){
                return 0;
            }
            return count;
            
        }
    }
    

Log in to reply
 

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