两种解法解决LCR 008. 长度最小的子数组【C++】

简介: 两种解法解决LCR 008. 长度最小的子数组【C++】


LCR 008. 长度最小的子数组

解法

暴力解法

//暴力解法:
//使用双for循环依次遍历数组,罗列出所有情况,然后判断
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        //  (min_length < j-i+1)因为下面进行比较的时候新长度更小才会进行更新,所以置为
        //  最大的值又不超出数组元素的最大取值
        int min_length = INT_MAX;
        int sum = 0;
        int size = nums.size();
        for(int i=0; i<size; i++)
        {
            sum=0;  //sum置零容易遗忘,切记
            for(int j=i; j<size; j++)
            {
                sum += nums[j];
                //依次相加,直到第一次sum大于target为止
                if(sum >= target)
                {
                    //取最小长度
                    min_length = (min_length < j-i+1) ? min_length : j-i+1;
                    break;  //当大于目标值以后,也就不需要继续比较了
                }
                
            }
        }
        //  如果min_length一次也没有用更新就返回零
        return min_length == INT_MAX ? 0 : min_length;
    }
};

滑动窗口(双指针法)

//  滑动窗口法
//  窗口的起始位置cur移动规则:当子数组之和sum大于target时,cur++并且记录此时子数组的长度
//  窗口的终点位置dest移动规则: 当子数组之和sum小于target时,dest++
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int dest = 0; //    指向窗口终点
        int cur = 0;//  指向窗口起点
        int size = nums.size();
        int sum = 0;
        int min_length = INT_MAX;
        
        //循环结束条件应当是dest遍历完数组并且窗口已经缩短到最小状态(这个放在二层循环里面更为合适)
        while(dest < size)
        {
            sum+=nums[dest];
            //一种情况就是sum>=target,此时并不能直接结束缩短窗口,min_length
            //还可能更小,所以再套一层循环
            while(sum >= target)
            {
                min_length = dest-cur+1 < min_length ? dest-cur+1 : min_length;
                //窗口缩短一次,sum也一定要更新
                sum -= nums[cur];
                cur++;
            }
            dest++;
        }
        return min_length == INT_MAX ? 0 : min_length;
    }
};

😄 创作不易,你的点赞和关注都是对我莫大的鼓励,再次感谢您的观看😄

相关文章
|
1月前
|
C++
两种解法解决 LeetCode 27. 移除元素【C++】
两种解法解决 LeetCode 27. 移除元素【C++】
|
6月前
|
算法 测试技术 C#
C++前缀和算法的应用:统计中位数为 K 的子数组
C++前缀和算法的应用:统计中位数为 K 的子数组
|
6月前
|
算法 测试技术 C#
C++前缀和算法的应用:统计得分小于K的子数组数目
C++前缀和算法的应用:统计得分小于K的子数组数目
|
1月前
|
C++
面向对象的C++题目以及解法2
面向对象的C++题目以及解法2
35 1
|
1月前
|
C++
面向对象的C++题目以及解法
面向对象的C++题目以及解法
22 0
|
1月前
|
人工智能 C++
查找题(二分解法c++)
查找题(二分解法c++)
31 0
|
1月前
|
安全 C++
石头剪子布(字符串解法 C++)
石头剪子布(字符串解法 C++)
22 0
|
1月前
|
C++ 容器
约瑟夫经典问题C++,STL容器queue解法
约瑟夫经典问题C++,STL容器queue解法
16 0
|
1月前
|
算法 C++ 索引
寻找最接近子数组和的算法设计及其C++实现
寻找最接近子数组和的算法设计及其C++实现
21 4
|
1月前
|
算法 测试技术 C#
C++单调向量(栈):好子数组的最大分数
C++单调向量(栈):好子数组的最大分数
C++单调向量(栈):好子数组的最大分数

热门文章

最新文章