Easy

题目描述

给你一个整数数组 nums 和两个整数 l 和 r。你的任务是找到一个子数组，其长度在 l 和 r 之间（包含边界），且和大于 0 的最小和。

返回这样的子数组的最小和。如果不存在这样的子数组，返回 -1。

子数组是数组中连续的非空元素序列。

示例 1：

输入：nums = [3, -2, 1, 4], l = 2, r = 3
输出：1
解释：
长度在 l = 2 和 r = 3 之间且和大于 0 的子数组有：
- [3, -2] 和为 1
- [1, 4] 和为 5  
- [3, -2, 1] 和为 2
- [-2, 1, 4] 和为 3

其中，子数组 [3, -2] 的和为 1，是最小的正和。因此答案是 1。

示例 2：

输入：nums = [-2, 2, -3, 1], l = 2, r = 3  
输出：-1
解释：
没有长度在 l 和 r 之间且和大于 0 的子数组。所以答案是 -1。

示例 3：

输入：nums = [1, 2, 3, 4], l = 2, r = 4
输出：3
解释：
子数组 [1, 2] 长度为 2，和为 3，是最小的正和。所以答案是 3。

约束条件：

  • 1 <= nums.length <= 100
  • 1 <= l <= r <= nums.length
  • -1000 <= nums[i] <= 1000

解题思路

这是一个经典的子数组和问题，由于数据规模较小（n ≤ 100），我们可以使用暴力枚举的方法。

解题思路

方法一：暴力枚举（推荐）

  • 枚举所有可能的子数组起始位置 i
  • 对于每个起始位置，枚举长度从 l 到 r 的所有子数组
  • 计算每个子数组的和，如果和大于 0，更新最小值
  • 时间复杂度 O(n²)，空间复杂度 O(1)

方法二：滑动窗口优化

  • 可以对每个长度 len（从 l 到 r）使用滑动窗口
  • 但由于数组中可能有负数，滑动窗口的优化效果有限
  • 在本题的约束下，暴力方法更简洁直观

实现要点：

  1. 外层循环枚举起始位置
  2. 内层循环从当前位置开始累加，长度达到 l 时开始检查
  3. 如果和大于 0，更新最小值
  4. 注意边界条件和初始值设置

代码实现

class Solution {
public:
    int minimumSumSubarray(vector<int>& nums, int l, int r) {
        int n = nums.size();
        int minSum = INT_MAX;
        bool found = false;
        
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n && j - i + 1 <= r; j++) {
                sum += nums[j];
                int len = j - i + 1;
                if (len >= l && sum > 0) {
                    minSum = min(minSum, sum);
                    found = true;
                }
            }
        }
        
        return found ? minSum : -1;
    }
};

class Solution:
    def minimumSumSubarray(self, nums: List[int], l: int, r: int) -> int:
        n = len(nums)
        min_sum = float('inf')
        found = False
        
        for i in range(n):
            current_sum = 0
            for j in range(i, min(n, i + r + 1)):
                current_sum += nums[j]
                length = j - i + 1
                if length >= l and current_sum > 0:
                    min_sum = min(min_sum, current_sum)
                    found = True
        
        return min_sum if found else -1

public class Solution {
    public int MinimumSumSubarray(IList<int> nums, int l, int r) {
        int n = nums.Count;
        int minSum = int.MaxValue;
        bool found = false;
        
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n && j - i + 1 <= r; j++) {
                sum += nums[j];
                int len = j - i + 1;
                if (len >= l && sum > 0) {
                    minSum = Math.Min(minSum, sum);
                    found = true;
                }
            }
        }
        
        return found ? minSum : -1;
    }
}

var minimumSumSubarray = function(nums, l, r) {
    const n = nums.length;
    let minSum = Infinity;
    let found = false;
    
    for (let i = 0; i < n; i++) {
        let sum = 0;
        for (let j = i; j < n && j - i + 1 <= r; j++) {
            sum += nums[j];
            const len = j - i + 1;
            if (len >= l && sum > 0) {
                minSum = Math.min(minSum, sum);
                found = true;
            }
        }
    }
    
    return found ? minSum : -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n²)
空间复杂度O(1)

其中 n 是数组长度。我们需要枚举所有可能的子数组，最坏情况下需要检查 O(n²) 个子数组。

相关题目