总和为 k 的子数组的最小大小

Question

我需要找到总和大于或等于< code>k的最小子阵列长度。数组将只有正数。

例如

输入:< code>target = 7，< code>nums = [2，3，1，2，4，3]输出:2说明:子数组[4，3]在问题约束下长度最小。

在我的代码中，对于输入:< code>target = 7，< code>nums = [2，3，1，2，4，3]我得到的答案是< code>3，但正确答案是< code>2。怎么修？

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

Answer 1

推进开始后，您必须在增加结束之前检查是否击中了traget;。您还可以使用 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;
    
}

Answer 2

我建议将时的外部转换为

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