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

Question

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

如

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.

在我的代码中，对于输入：target = 7、nums = [2,3,1,2,4,3] 我得到的答案是 3，但正确答案是 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

推进开始后，您必须在增加 end++; 之前检查是否击中目标。您还可以使用 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

我建议将外部 while 变成 for 这有助于简化 (Java) 代码:

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

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

Minimum size of subarray whose sum is k

language-agnostic

arrays

algorithm

data-structures