基于leetcode的算法训练：Day3

2.4 和大于等于 target 的最短子数组

**题目要求：**给定一个含有 n 个正整数的数组和一个正整数 target 。

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

题目链接：剑指 Offer II 008. 和大于等于 target 的最短子数组 - 力扣（LeetCode）

**题目难度：**✨✨

AC题解

直接暴力求解了捏~

首先计算前缀和，接着从index=0开始遍历符合要求>=target的前缀和，并且在此基础上更新计算更小的长度，注意剪枝

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        //返回连续最小子数组的个数
        int len=nums.size();
        int ans=0;
        int min_len=len;
        int cnt=0;
        vector<int>preSum(len);
        //试试暴力
        for(int i=0;i<len;i++){
            if(i){
                preSum[i]=preSum[i-1]+nums[i];
            }else{
                preSum[i]=nums[i];
            }
        }
        if(preSum[len-1]<target){
            return 0;
        }
        for(int i=0;i<len;i++){
            if(preSum[i]>=target){
                int j=0;
                if(i-j+1>min_len){
                    j=i-min_len+1;//剪枝操作
                }
                //i-j的
                while(j<len&&preSum[i]-preSum[j]+nums[j]>=target){
                    if(i-j+1<min_len){
                        min_len=i-j+1;
                        ans=1;
                    }else if(i-j+1==min_len){
                        ans++;
                    }
                    j++;
                }
            }
        }
        return min_len;
    }
};
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
30
31
32
33
34
35
36
37
38
39
40
41

2.5 乘积小于K的子数组个数

题目要求：给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。

题目链接：剑指 Offer II 009. 乘积小于 K 的子数组 - 力扣（LeetCode）

题目难度：✨✨✨

暴力题解，但是会超时

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        //乘积小于k的连续子数组的个数
        int len=nums.size();
        int ans=0;
        int cnt;
        for(int i=0;i<len;i++){
            if(nums[i]>=k){
                continue;
            }else{
                ans++;
                cnt=nums[i];
                for(int j=i+1;j<len;j++){
                    cnt*=nums[j];
                    if(cnt>=k){
                        break;
                    }
                    ans++;
                }
            }

        }
        return ans;
    }
};
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

官方题解

两种思路：

• 二分法用log求解
• 滑动窗口

我选择用后者，因为更简洁且效率更高~

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        //乘积小于k的连续子数组的个数
        int len=nums.size();
        int ans=0;
        int cnt=1;
        //找到尽可能长的一段i-j
        //滑动窗口
        int right,left=0;
        for(right=0;right<len;right++){
            cnt*=nums[right];
            while(left<=right&&cnt>=k){
                cnt/=nums[left];
                left++;//滑动窗口的左节点
            }
            ans+=(right-left+1);
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22