力扣—长度最小的子数组

文章目录

- 题目解析
- 解题思路
- 代码实现

题目解析

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的
子数组
[numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

解题思路

暴力解法，我们可以找出所有的子数组，然后再求解。但是时间复杂度高，不适合。不过我们在子数组的过程可以发现一些规律，得到一些优化。例如 nums = [2,3,1,2,4,3]，target = 7,当我们找到子数组[2,3,1,2]，这个子数组已经满足里题目要求，如果我们再在这个子数组的基础上向后遍历加上其他数字变为[2,3,1,2,4]，（正整数的数组）虽然同样也满足题目要求但数组长度明显会大于前一个数组，所以这样的子数组我们应该排除掉。直接找满足target的最小数组就可以了。

这种用同向指针（两个指针同时向前或后移动），方法有个名字叫滑动窗口。

代码实现

Java实现

class Solution {
    public int minSubArrayLen(int target, int[] nums) 
    {
     int n=nums.length;
     int i=0,j=0,sum=0;
     int length=1000000;
     int ret=0;
     while(j<n)
     {
        sum=sum+nums[j];
        while(sum>=target)
        {
         ret=j-i+1;
         length=Math.min(length,ret);
         sum=sum-nums[i++];
        }
        j++;
     }
     if(ret==0)
     {
        return 0;
     }
     return length;
    }
}

解释代码

int n = nums.length;
int i = 0, j = 0;  // i 和 j 分别表示子数组的起始和结束位置
int sum = 0;       // sum 表示当前子数组的和
int length = 1000000;  // 初始化一个较大的长度值，用于记录最短子数组的长度
int ret = 0;       // ret 用于记录当前子数组的长度

while (j < n) {
    sum = sum + nums[j];
    while (sum >= target) {
        ret = j - i + 1;  // 计算当前子数组的长度
        length = Math.min(length, ret);  // 更新最短子数组的长度
        sum = sum - nums[i++];  // 移动左指针，缩小子数组范围，更新和
    }
    j++;  // 移动右指针，扩大子数组范围
}

if (ret == 0) {
    return 0;  // 如果没有找到满足条件的子数组，返回 0
}
return length;  // 返回最短子数组的长度

在这里插入图片描述
C语言实现

int minSubArrayLen(int target, int* nums, int numsSize) 
{
    int i=0;
	int j=0;
	int sum=0;
	int ret=INT_MAX;
	int length=0;
    for(j=0;j<numsSize;j++)
    {
		sum+=nums[j];
    	while(sum>=target)
		{
			length=j-i+1;
			ret=ret>length?length:ret;
			sum=sum-nums[i++];
		}
	}

    if(length==0)
    {
		return 0;
	}
	else
	{
		return ret;
	}
}