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

Minimum size of subarray whose sum is k

提问人：Pale Blue Dot 提问时间：5/16/2022 最后编辑：Dmitry BychenkoPale Blue Dot 更新时间：6/26/2023 访问量：302

问：

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

例如

输入： ， 输出： 2 解释： 子数组 [4,3] 在问题约束下具有最小长度。target = 7nums = [2,3,1,2,4,3]

在我的代码中，对于 Input： ，我得到的答案是 ，但正确的答案是 。如何解决？target = 7nums = [2,3,1,2,4,3]32

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;
        
    }
数组 算法 数据结构 与语言无关

评论

答：

1赞 Goswin von Brederlow 5/16/2022 #1

推进开始后，您必须在递增之前检查是否命中了 traget。您还可以使用 goto 避免一些代码重复。end++;

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

评论

0赞 Pale Blue Dot 5/16/2022
else if ( sum > target) { while (start<= end && sum > target) { sum = sum - nums[start]; start++; } if (sum == target) { minArraySize = Math.min(minArraySize, end - start + 1); end++; }我做了同样的事情。但是算法仍然不起作用
0赞 Goswin von Brederlow 5/16/2022
对我有用 godbolt.org/z/zhjPvWej6
0赞 Pale Blue Dot 5/16/2022
刚刚运行了你的代码 inleetcode。它未能通过某些测试用例（就像我的解决方案一样）。https://leetcode.com/problems/minimum-size-subarray-sum/
0赞 Goswin von Brederlow 5/16/2022
也许你需要处理？target <= 0
1赞 Goswin von Brederlow 5/16/2022
不，这是示例 3 中的“未找到”情况。我们返回 IN_MAX，但预期为 0。坦率地说，这是没有道理的。
1赞 Dmitry Bychenko 5/16/2022 #2

我建议将 outer 转换为可以帮助简化 （Java） 代码：whilefor

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

评论

0赞 Pale Blue Dot 5/16/2022
我试过你的soltion。测试用例失败 leetcode.com/problems/minimum-size-subarray-sum
0赞 Dmitry Bychenko 5/16/2022
@Pale 蓝点：我明白了;如果没有找到Subarry，我们应该返回。我已经编辑了答案0
0赞 Pale Blue Dot 5/16/2022
它有效。我无法输入'Target ：11 and Nums[] ： {1,2,3,4,5} 。输出如何是 3？
1赞 Dmitry Bychenko 5/16/2022
@Pale Blue Dot：引自 Leetcode：“......总和大于或等于......“，粗体是我的，这就是为什么我们有答案，因为（注意而不是33 + 4 + 5 >= 11>===)
0赞 Pale Blue Dot 5/16/2022
啊，我错过了“大于”的部分。难怪我的代码不适用于所有输入。谢谢

上一个：继承总是可以被组合物取代吗？

下一个：空间邻近度查询的数据结构