【算法挨揍日记】day05——209. 长度最小的子数组、3. 无重复字符的最长子串

亦凉 2024-03-03 08:23 7阅读 0赞

![b679dbfd707c4bd6b310601c4de5f7b0.png][]

## 209. 长度最小的子数组 ##

[209. 长度最小的子数组][209.]

### 题目描述： ###

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

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

![000ec9e64b204ccc8ee1530fdb6f8e36.png][]

### 解题思路： ###

> 我们通过题目得知，本题是一个正数数列，题目要求求出最小连续子数组，假设子数组之和为sum
> 
> ![eda36ef1cd7440ab93834828e08fc61e.png][]
> 
> 假设从左到右，我们每加一个数，sum都是增大，每减一个数，sum都是减小，这就是具有**单调性**
> 
> 所以我们可以用两个指针left和right（一开始都是在0的位置）来当做窗口的左右边界，当right向右移动的时候，sum为这个窗口之和，当right向右，sum递增，当left向右，sum递减（当双指针运动方向相同的时候称为同向双指针），当sum>=target，出窗口（left++），否则进窗口（right++），还需要更新length（最小长度）。
> 
> 时间复杂度：虽然代码是两层循环，但是我们的  left  指针和  right  指针都是不回退的，两者 
> 
> 最多都往后移动  n  次。因此时间复杂度是  O(N)  。

### 解题代码: ###

class Solution {
    public:
        int minSubArrayLen(int target, vector<int>& nums) {
            int length = INT_MAX;
            int n = nums.size();
            int left = 0;
            int right = 0;
            int sum = 0;
            while(right<n)
            {
                sum+=nums[right];
                while(sum>=target)
                {
                    length=min(length,right-left+1);
                    sum-=nums[left++];
                }
                right++;
            }
            return length==INT_MAX?0:length;
        }
    };

--------------------

## 3. 无重复字符的最长子串 ##

[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/a3d3e2fb96884c5b8109c604bf7fbc10.png][LeetCode_ - _ IT _ Dream Offer_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_leetcode.cn_problems_longest-substring-without-repeating-characters]

### 题目描述： ###

给定一个字符串 `s` ，请你找出其中不含有重复字符的 **最长子串** 的长度。

### ![f7828e3e6e2a4c5cadd035851771bcd2.png][] 解题思路： ###

依旧是利用滑动窗口

### 解题代码： ###

class Solution {
    public:
        bool str(string&s,int left,int right,char ch)
        {
            for(int i=left;i<=right;i++)
            {
                if(ch==s[i])
                return false;
            }
            return true;
        }
        int lengthOfLongestSubstring(string s) {
            int length=0;
            int left=0,right=0;
            int n=s.size();
            while(right<n)
            {
                while(!str(s,left,right-1,s[right]))
                    left++;
                length=max(length,right-left+1);
                right++;
            }
            return length;
        }
    };

![8714b031ab004b61acc4ed0dc0453649.gif][]

[b679dbfd707c4bd6b310601c4de5f7b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/e4a14e2382e64941a11e779cd345e6fb.png
[209.]: https://leetcode.cn/problems/minimum-size-subarray-sum/
[000ec9e64b204ccc8ee1530fdb6f8e36.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/d0f142361b0e46c895d526a1fd81d8f0.png
[eda36ef1cd7440ab93834828e08fc61e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/b28db28f1c4d44e5b6e0b717ccacd266.png
[icon-default.png_t_N7T8]: https://csdnimg.cn/release/blog_editor_html/release2.3.6/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N7T8
[LeetCode_ - _ IT _ Dream Offer_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_leetcode.cn_problems_longest-substring-without-repeating-characters]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/a3d3e2fb96884c5b8109c604bf7fbc10.png
[f7828e3e6e2a4c5cadd035851771bcd2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/8ad2402b7c68490e8970e776a87628b7.png
[8714b031ab004b61acc4ed0dc0453649.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/e7ee65c252a1427c93f139b8070d3aea.png