給定一個含有n?個正整數(shù)的數(shù)組和一個正整數(shù)s ，找出該數(shù)組中滿足其和?≥ s?的長度最小的連續(xù)子數(shù)組。如果不存在符合條件的連續(xù)子數(shù)組，返回 0。

示例:?

輸入:s = 7, nums = [2,3,1,2,4,3]輸出:2解釋: 子數(shù)組[4,3]是該條件下的長度最小的連續(xù)子數(shù)組。

進階:

如果你已經(jīng)完成了O(n) 時間復(fù)雜度的解法, 請嘗試O(n?log?n) 時間復(fù)雜度的解法

題目

class Solution {

public:

? ? //時間復(fù)雜度O（n）

? ? //空間復(fù)雜度O(1)

? ? int minSubArrayLen(int s, vector<int>& nums) {

? ? ? ? int l=0,r=-1;//nums[l...r]為我們的滑動窗口

? ? ? ? int sum=0;

? ? ? ? int res=nums.size()+1;//這是為了以后取最小值，這個初始化的值顯然不可能取到

? ? ? ? while(l<nums.size()){

? ? ? ? ? ? if(r+1<nums.size()&&sum<s){ //r+1<nums.size()是為了防止越界

? ? ? ? r++;

? ? ? ? sum+=nums[r];

? ? ? ? ? ? }

? ? ? ? else{

? ? ? ? ? ? sum-=nums[l];

? ? ? ? ? ? l++;}

? ? ? ? if(sum>=s)

? ? ? ? ? ? res=min(res,r-l+1);

? ? ? ? }

? ? ? if(res==nums.size()+1)

? ? ? ? ? return 0;

? ? ? ? return res;

? ? }

};

滑動窗口思想

給定一個字符串，找出不含有重復(fù)字符的最長子串的長度。

示例?1:

輸入: "abcabcbb"輸出: 3解釋:無重復(fù)字符的最長子串是"abc"，其長度為 3。

示例 2:

輸入: "bbbbb"輸出: 1解釋: 無重復(fù)字符的最長子串是"b"，其長度為 1。

示例 3:

輸入: "pwwkew"輸出: 3解釋: 無重復(fù)字符的最長子串是"wke"，其長度為 3。?? ? 請注意，答案必須是一個子串，"pwke"是一個子序列 而不是子串

無重復(fù)字符的最長子串

class Solution {

public:

? ? int lengthOfLongestSubstring(string s) {

? ? ? ? int freq[256]={0};//這是設(shè)個計數(shù)器，里面裝ascal碼，如果出現(xiàn)就加一

? ? ? ? ? int l=0,r=-1;//nums[l...r]為我們的滑動窗口

? ? ? ? int res=0;

? ? ? ? while(l<s.size()){

? ? ? ? ? ? if(r+1<s.size()&&freq[s[r+1]]==0){//設(shè)的flag為

? ? ? ? ? ? ? ? r++;

? ? ? ? ? ? ? ? freq[s[r]]++;//這時都是窗口右邊界滑動

? ? ? ? ? ? }

? ? ? ? ? ? else{

? ? ? ? ? ? ? ? freq[s[l]]--;//這樣就表示遇到相同的一個字母，重置，計數(shù)器--窗口左邊界滑動

? ? ? ? ? ? l++;

? ? ? ? ? ? }

? ? ? ? ? ? res=max(res,r-l+1);

? ? ? ? }

? ? ? ? return res;

? ? }

};

解答

類似的題還有LeetCode里438和76（較難）道題。可以使用滑動窗口思想。