当前位置: 面试刷题>> 长度最小的子数组(经典算法150题)


题目描述

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

示例 1:

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

示例 2:

输入: nums = [1], target = 0
输出: 1

示例 3:

输入: nums = [1, 2, 3], target = 4
输出: 0
解释: 没有找到符合条件的子数组,返回 0。

PHP 示例代码

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

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

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

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

// 示例用法
$nums = [2, 3, 1, 2, 4, 3];
$target = 6;
echo minSubArrayLen($nums, $target); // 输出 2

Python 示例代码

def minSubArrayLen(nums, target):
    min_len = float('inf')
    sum_ = 0
    start = 0

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

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

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

# 示例用法
nums = [2, 3, 1, 2, 4, 3]
target = 6
print(minSubArrayLen(nums, target))  # 输出 2

JavaScript 示例代码

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

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

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

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

// 示例用法
const nums = [2, 3, 1, 2, 4, 3];
const target = 6;
console.log(minSubArrayLen(nums, target)); // 输出 2

以上三种语言的代码都使用了滑动窗口的思想来解决这个问题,通过维护一个窗口的起始和结束位置来寻找符合条件的最小长度子数组。希望这能帮助你理解并解答这道面试题。

推荐面试题