长度最小的数组

209

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

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

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

#include <iostream>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int right = nums.size();
        if(right == 0){
            return 0;
        }
        int ans = INT_MAX;
//        vector<int> sums(right+1,0);//要多一个长度，前缀和
        int *sums = (int *)malloc(sizeof(int) * (right + 1));
        //计算前缀和
        for(int i =1; i<=right; i++){
            sums[i] = sums[i-1]+nums[i-1];//太妙了，这样就可以计算前缀和了
        }
        //二分法
        for(int i = 1;i <= right; i++){
            int mid = target+sums[i-1];
            int bound = lower_bounds(sums, 1, right, mid);
            if(bound != -1){
                ans=min(ans,(bound - ( i - 1 )));
            }
        }
        return ans ==  INT_MAX ? 0 : ans;
    }
    int lower_bounds(int *array, int l, int r, int q) {
        if (array[r] < q) return -1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (array[mid] >= q) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

int main(){
    vector<int> nums={2,3,1,2,4,3};
    Solution *solution;
    printf("%d",solution->minSubArrayLen(7,nums));
}

滑动窗口的办法

确定如何移动起始位置

由于是取最小的，所以使用函数min

持续向后移动起始位置，更新sum

#include <iostream>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
     int minSubArrayLen(int target, vector<int>& nums) {
        int len = nums.size();
        int sum = 0;
        int index = 0;
        int ans = INT_MAX;
        for(int i = 0;i <= len -1; i++){
            sum += nums[i];//求和
            while(sum >= target){//大于target，往前减小找到符合的区间
                int len = i-index + 1;//当前窗口的长度
                sum -= nums[index];
                ans = min(ans,len);//取最小的
                index++;

            }
        }
        return ans==INT_MAX ? 0 : ans;
    }
};

int main(){
    vector<int> nums={2,3,1,2,4,3};
    Solution *solution;
    printf("%d",solution->minSubArrayLen(7,nums));
}