• leetcode面试经典150题——30 长度最小的子数组


    题目:长度最小的子数组

    描述
    给定一个含有 n 个正整数的数组和一个正整数 target 。

    找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

    示例 1:

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

    leetcode链接

    方法一:滑动窗口
    滑动窗口有两种:一种是固定大小的窗口,另一种是动态大小的窗口,而本题要求长度最小的子数组,所以应该用动态大小的窗口,滑动窗口基于双指针的思想:
    我们定义两个指针left和right表示窗口的两端,定义一个minLen变量表示最端短的长度,初始时指针都指向0,此时如果窗口内的数之和小于目标数target,那么right指针右移,窗口变大,相反如果窗口内的数之和大于目标数target,那么更新minLen,并且移动left指针,直到窗口内的数之和小于目标数target为止。最后遍历完数组,minLen即为长度最小的子数组
    时间复杂度;o(n)
    空间复杂度:o(1)

    int minSubArrayLen(int target, vector<int>& nums) {
            int n = nums.size();
            int minLen = n+1;
            int left = 0,right = 0;
            int sum = 0;
            while(right<n){
                sum+=nums[right];
                while(sum>=target){
                    minLen = min(minLen,right-left+1);
                    sum-=nums[left];
                    left++;
                }
                right++;
            }
            //如果minLen没有更新过,即为不存在满足条件的子数组,返回0
            return minLen==n+1?0:minLen;
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    方法二:暴力法
    我们枚举数组中的每一个元素为子数组的起始元素,然后找到从枚举的元素开始满足条件的最小子数组的长度,再维护最小的子数组长度,即可找到答案。
    时间复杂度:o(n²)
    空间复杂度:o(1)

    int minSubArrayLen(int s, vector<int>& nums) {
            int n = nums.size();
            if (n == 0) {
                return 0;
            }
            int ans = INT_MAX;
            for (int i = 0; i < n; i++) {
                int sum = 0;
                for (int j = i; j < n; j++) {
                    sum += nums[j];
                    if (sum >= s) {
                        ans = min(ans, j - i + 1);
                        break;
                    }
                }
            }
            return ans == INT_MAX ? 0 : ans;
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    方法三:前缀和+二分查找
    暴力法中枚举子数组起始元素的时间复杂度为o(n),找到最小子数组的时间复杂度为o(n),此时我们考虑优化寻找最小子数组的时间,注意到我们给定的数组的所有的元素都是大于0的,那么我们每一个元素的前缀和都是递增的,因此我们可以利用二分查找来查找最小子数组,如果我们枚举第i个元素为最小子数组的起始元素,那么我们二分查找的元素可以变为target+i的前缀和,而此时找到的目标元素的前缀和-i的前缀和 = target,因此我们找到的元素即为最短子数组的末尾,然后我们再维护最短的一个长度
    时间复杂度:o(nlogn) 二分查找的时间复杂度为logn
    空间复杂度:o(n) 存储前缀和的空间为o(n)
    注意:注意二分查找时的left和right指针的取值

    int minSubArrayLen(int target, vector<int>& nums) {
    	int n = nums.size();
    	int minLen = n+1,mid = 0;
    	vector<int> sum(n+1,0);
    	//sum[i]表示前i个数之和 
    	for(int i=1;i<=n;i++){
    		sum[i] = sum[i-1]+nums[i-1];
    	}
    	for(int i=1;i<=n;i++){
    		//枚举每个元素为子数组的起始元素
    		//注意i为第i个元素,而第i个元素的下标为i-1
    		int tag = target+sum[i-1];
    		//这里的left和right表示的为第几个元素,由于sum[i]为第i个元素的前缀和
    		int left = i,right = n;
    		while(left<right){
    			mid = (left+right)/2;
    			if(tag>sum[mid]){
    				left = mid+1;
    			}else{
    				//我们要找的数为大于等于tag,所以right=mid,而不是mid-1
    				right = mid;
    			}
    		}
    		if(sum[left]>=tag){
    			minLen = min(left-i+1,minLen);
    		}
    	}
    	return minLen==n+1?0:minLen;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
  • 相关阅读:
    使用显著性检测的可见光和红外图像的两尺度图像融合(Matlab代码实现)
    【深圳五兴科技】Java后端面经
    单片机常识篇
    Stable Diffusion中的ControlNet插件
    商业化广告--体系学习-- 2 -- 行业蓝图篇 -- 广告产品与商业模式
    Pr:更改剪辑的速度和持续时间
    【算法系列篇】分治-快排
    python+django+vue某小区物业管理系统
    redis 事务,深入解读
    百趣代谢组学资讯:寻求多年,黄瓜品质好的秘密居然在这里
  • 原文地址:https://blog.csdn.net/weixin_48144140/article/details/134539112