leetcode
leetcode 2901 ~ 2950
长度最小的子数组

长度最小的子数组

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 26 ms, 内存: 17.7 MB


/*
 * 思路:虽然Java Stream不太适合这种需要双指针滑动窗口的算法,但我们可以用Stream来解决辅助部分。
 * 具体的滑动窗口部分仍需要使用传统的循环方式。
 */

import java.util.stream.IntStream;

public class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;
        int sum = 0;
        int start = 0;
        for (int end = 0; end < n; end++) {
            sum += nums[end];
            while (sum >= target) {
                minLength = Math.min(minLength, end - start + 1);
                sum -= nums[start++];
            }
        }
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}

解释

方法:

这个题解采用了滑动窗口(双指针)的方法,来寻找数组中的最小连续子数组,其和大于等于给定的target。方法中,我们定义两个指针left和right,表示子数组的左右边界。从头开始遍历数组,逐渐扩展right指针来增加子数组的和。每当子数组的和达到或超过target时,尝试通过移动left指针来缩小窗口大小,直到子数组的和小于target。在此过程中,我们记录达到条件的最小子数组长度。整个过程中,每个元素只会被访问两次(一个添加到窗口,一个从窗口中移除),因此时间效率较高。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
算法为什么在总和达到或超过target时尝试通过缩小左边界来寻找最小长度,而不是继续增加右边界?
当总和达到或超过目标值target时,继续增加右边界只会进一步增加子数组的长度,这与寻找最小长度的目标相悖。通过缩小左边界(即移动left指针向右),我们可以尝试减小数组的长度而不是增加,从而找到可能的最小长度满足条件的子数组。
🦆
在算法中,如果总和刚好等于target,为何仍要尝试移动左指针来缩小窗口?这样做的目的是什么?
即使总和刚好等于target,我们仍然尝试缩小窗口是为了探索是否存在更小的符合条件的子数组。可能存在某些元素的值较大,导致移动左指针后,即使减少了一些元素,总和仍然能满足条件。这样,我们可以确保找到的是真正的最小长度子数组。
🦆
当数组中的所有元素之和仍小于target时,算法的返回值为0。在这种情况下,是否有必要遍历完整个数组?
有必要遍历整个数组,因为我们无法事先知道数组的总和是否达到target,除非遍历完所有元素。此外,即使在遍历的过程中总和一度未达到target,我们也需要确认这一点以确实不存在任何子数组能满足条件,从而准确返回0。

相关问题