Minimum size of subarray whose sum is k-CodePudding

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

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;
        
    }

CodePudding user response：

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;
    
}

CodePudding user response：

I suggest turning outer while into for which can help to simplify the 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];
                    
        while (sum >= target) {
            result = result == 0
                ? right - left   1
                : Math.min(result, right - left   1); 

            sum -= nums[left  ];
        }
    }
    
    return result;
}

CodePudding user response：

You should sort input array items descending then try your algorithm.