Minimum size of subarray whose sum is k

user_12138049 0
Viewed 89

I need to find minimum subarray length whose sum is greater or equal to k. Array will have only positive numbers.

eg

Input: target = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: The subarray [4,3] has the minimal length under the problem constraint.

In my code, for Input: target = 7, nums = [2,3,1,2,4,3] I am getting answer as 3, but the right answer is 2. How to fix it?

public int minSubArrayLen(int target, int[] nums) {
    
        int arraySize = nums.length;
        int end = 0; // end of subarray
        int start = 0; // start of subarray
        int minArraySize = Integer.MAX_VALUE;
        int sum = 0;

        while (end < arraySize) {
            sum = sum + nums[end];
            if (sum == target) {
                minArraySize = Math.min(minArraySize, end - start + 1);
                end++;
            } else if (sum > target) {
                while (sum > target) {
                    sum = sum - nums[start];
                    start++;
                }
                  
                  end++;


                if (sum == target)
                {
                  minArraySize  = Math.min(minArraySize, end - start +1);
                }

                    

            } else if (sum < target) {
                end++;

            }
        }
     
         
        return minArraySize;
        
    }
data-structures language-agnostic arrays algorithm
2 Answers

After advancing the start you have to check if you hit the traget before you increment end++;. You can also avoid some code duplication with a goto.

int minSubArrayLen(int target, std:vector<int> nums) {
    int arraySize = nums.size();
    int end = 0; // end of subarray
    int start = 0; // start of subarray
    int minArraySize = INT_MAX;
    int sum = 0;

    while (end < arraySize) {
        sum = sum + nums[end];
    again:
        if (sum == target) {
            minArraySize = Math.min(minArraySize, end - start + 1);
        } else if (sum > target) {
            sum = sum - nums[start];
            start++;
            goto again;
        } 
        end++;
    }
 
     
    return minArraySize;
    
}
user_42623440

I suggest turning outer while into for which can help to simplify the (Java) code:

public int minSubArrayLen(int target, int[] nums) {
    //TODO: check for nums == null, target <= 0
    
    int result = 0;
    
    int left = 0;
    int sum = 0;
    
    for (int right = 0; right < nums.length; ++right) {
        sum += nums[right];
                 
        // if sum is large enough we should subtract from the left   
        while (sum >= target) {
            result = result == 0
                ? right - left + 1
                : Math.min(result, right - left + 1); 

            sum -= nums[left++];
        }
    }
    
    return result;
}
user_23194070
Related