当前位置: 面试刷题>> 最小子数组 (经典算法题500道)


题目描述补充

题目:最小子数组

给定一个整数数组 nums 和一个整数 target,请你在该数组中找出和为目标值 target 的那 连续、非空 的子数组,并返回其最小长度。如果不存在这样的子数组,则返回 0。

注意

  • 数组中的元素可能包含负数。
  • 数组中的元素可能重复。
  • 数组至少包含一个元素。

示例

输入nums = [2, 3, 1, 2, 4, 3], target = 6 输出2 解释:子数组 [2, 4] 的和是 6,且长度最小。

PHP 示例代码

function minSubArrayLen($nums, $target) {
    $minLength = PHP_INT_MAX;
    $sum = 0;
    $start = 0;

    for ($end = 0; $end < count($nums); $end++) {
        $sum += $nums[$end];

        while ($sum >= $target) {
            $minLength = min($minLength, $end - $start + 1);
            $sum -= $nums[$start];
            $start++;
        }
    }

    return $minLength == PHP_INT_MAX ? 0 : $minLength;
}

// 测试
$nums = [2, 3, 1, 2, 4, 3];
$target = 6;
echo minSubArrayLen($nums, $target); // 输出 2

Python 示例代码

def minSubArrayLen(nums, target):
    minLength = float('inf')
    sum = 0
    start = 0

    for end in range(len(nums)):
        sum += nums[end]

        while sum >= target:
            minLength = min(minLength, end - start + 1)
            sum -= nums[start]
            start += 1

    return minLength if minLength != float('inf') else 0

# 测试
nums = [2, 3, 1, 2, 4, 3]
target = 6
print(minSubArrayLen(nums, target))  # 输出 2

JavaScript 示例代码

function minSubArrayLen(nums, target) {
    let minLength = Infinity;
    let sum = 0;
    let start = 0;

    for (let end = 0; end < nums.length; end++) {
        sum += nums[end];

        while (sum >= target) {
            minLength = Math.min(minLength, end - start + 1);
            sum -= nums[start];
            start++;
        }
    }

    return minLength === Infinity ? 0 : minLength;
}

// 测试
const nums = [2, 3, 1, 2, 4, 3];
const target = 6;
console.log(minSubArrayLen(nums, target)); // 输出 2

码小课网站中有更多关于算法和数据结构的内容分享,欢迎大家学习交流。

推荐面试题