第一題：長(zhǎng)度最小的子數(shù)組

力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)

思路：

第一想法肯定時(shí)暴力枚舉，枚舉數(shù)組任何一個(gè)元素，把他當(dāng)起始位置，然后從起始位置找最短區(qū)間，使得區(qū)間和大于等于目標(biāo)值

利用兩個(gè)嵌套for循環(huán)，如果符合條件就記錄，然后更新結(jié)果，返回

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {// 記錄結(jié)果int ret = INT_MAX;int n = nums.size();// 枚舉出所有滿(mǎn)?和?于等于 target 的?數(shù)組[start, end]// 由于是取到最?，因此枚舉的過(guò)程中要盡量讓數(shù)組的?度最?// 枚舉開(kāi)始位置for (int start = 0; start < n; start++){int sum = 0; // 記錄從這個(gè)位置開(kāi)始的連續(xù)數(shù)組的和// 尋找結(jié)束位置for (int end = start; end < n; end++){sum += nums[end]; // 將當(dāng)前位置加上if (sum >= target) // 當(dāng)這段區(qū)間內(nèi)的和滿(mǎn)?條件時(shí){// 更新結(jié)果，start 開(kāi)頭的最短區(qū)間已經(jīng)找到ret = min(ret, end - start + 1);break;}}}// 返回最后結(jié)果return ret == INT_MAX ? 0 : ret;}
};

由于都是正數(shù)因此，只要找到最短區(qū)間就不必往下繼續(xù)查找，因?yàn)榭赡芩械臄?shù)都不滿(mǎn)足條件，因此這里可能返回0，并且保證所有數(shù)都可更新，初始化ret為INT_MAX;

法二：滑動(dòng)窗口

先將右端元素劃入窗口，然后統(tǒng)計(jì)窗口元素和，如果大于target，更新，并且把左端元素滑出，繼續(xù)同時(shí)判斷是否滿(mǎn)足更新結(jié)果，因?yàn)榛鋈ブ鸵琅f可能滿(mǎn)足條件，如果窗口不滿(mǎn)足right++，進(jìn)入下一個(gè)窗口。

?

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

來(lái)自一個(gè)力扣大佬的形象解釋：左右指針中間窗口的sum為兩指針的“共同財(cái)產(chǎn)”，就是右指針一直在努力工作掙錢(qián)，好不容易共同財(cái)產(chǎn)大過(guò)target，記錄一下兩指針之間的距離，結(jié)果左指針就開(kāi)始得瑟揮霍，不?；ㄥX(qián)（往右移動(dòng)），結(jié)果花錢(qián)一直花到sum又小過(guò)target，此時(shí)右指針不得不再次出來(lái)工作，不停向右移動(dòng)，周而復(fù)始，最后取左右指針離得最近的時(shí)候

?

第二題：?重復(fù)字符的最??串（medium）

力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)

法一依舊是暴力：

即先固定一個(gè)，然后遍歷所有，創(chuàng)建個(gè)哈希表用來(lái)記錄出現(xiàn)的次數(shù)，如果大于一則說(shuō)明出現(xiàn)重復(fù)，那么就跳出當(dāng)前循環(huán)，進(jìn)入下一個(gè)固定的數(shù)進(jìn)行遍歷，否則就記錄此刻長(zhǎng)度

class Solution {
public:int lengthOfLongestSubstring(string s) {int ret = 0; // 記錄結(jié)果int n = s.length();// 1. 枚舉從不同位置開(kāi)始的最?重復(fù)?串// 枚舉起始位置for (int i = 0; i < n; i++){// 創(chuàng)建?個(gè)哈希表，統(tǒng)計(jì)頻次int hash[128] = { 0 };// 尋找結(jié)束為?for (int j = i; j < n; j++){hash[s[j]]++; // 統(tǒng)計(jì)字符出現(xiàn)的頻次if (hash[s[j]] > 1) // 如果出現(xiàn)重復(fù)的break;// 如果沒(méi)有重復(fù)，就更新 retret = max(ret, j - i + 1);}}// 2. 返回結(jié)果return ret;}
};

?

?法二：

例題中的 abcabcbb，進(jìn)入這個(gè)隊(duì)列（窗口）為 abc 滿(mǎn)足題目要求，當(dāng)再進(jìn)入 a，隊(duì)列變成了 abca，這時(shí)候不滿(mǎn)足要求。所以，我們要移動(dòng)這個(gè)隊(duì)列！如何移動(dòng)？我們只要把隊(duì)列的左邊的元素移出就行了，直到滿(mǎn)足題目要求！一直維持這樣的隊(duì)列，找出隊(duì)列出現(xiàn)最長(zhǎng)的長(zhǎng)度時(shí)候，求出解！

步驟就是右端ch元素進(jìn)入時(shí)，用哈希表統(tǒng)計(jì)次數(shù)，如果超過(guò)1，則有重復(fù)，那么從左側(cè)滑出窗口，直到ch次數(shù)變?yōu)?，然后更新。

如果沒(méi)有超過(guò)1，說(shuō)明沒(méi)有重復(fù)，直接更新

class Solution {
public:int lengthOfLongestSubstring(string s){int hash[128]={0};int left=0,right=0,n=s.size();int ret=0;while(right<n){hash[s[right]]++;while(hash[s[right]]>1)//判斷進(jìn)入{hash[s[left++]]--;//出窗口，然后左邊移動(dòng)}ret = max(ret,right-left+1);right++;//}return ret;}     
};

第三題：最大連續(xù)1的個(gè)數(shù)

力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)

思路：這題，

class Solution
{
public:int longestOnes(vector<int>& nums, int k){int ret = 0;for (int left = 0, right = 0, zero = 0; right < nums.size(); right++){if (nums[right] == 0) zero++; // 進(jìn)窗?while (zero > k) // 判斷if (nums[left++] == 0) zero--; // 出窗?ret = max(ret, right - left + 1); // 更新結(jié)果}return ret;}
}

?

?