Leetcode209. 長度最小的子數(shù)組

題目

Leetcode209. 長度最小的子數(shù)組

解法一(暴力求解)（超時(shí)）

暴力枚舉出所有子數(shù)組的和 O(n^2);

代碼

class Solution 
{
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int res = INT_MAX;// 記錄答案for(int i = 0; i < n; i++){int sum = 0;for(int j = i; j < n; j++){sum += nums[j];if(sum >= target){res = min(res, j - i + 1);break;}}}return res == INT_MAX ? 0 : res;}
};

解法二（滑動(dòng)窗口）

開始將右端元素劃?窗?中，統(tǒng)計(jì)出此時(shí)窗?內(nèi)元素的和：

• 如果窗?內(nèi)元素之和?于等于target ：更新結(jié)果，并且將左端元素劃出去的同時(shí)繼續(xù)判
  斷是否滿?條件并更新結(jié)果（因?yàn)樽蠖嗽乜赡芎苄?#xff0c;劃出去之后依舊滿?條件）
• 如果窗?內(nèi)元素之和不滿?條件： right++ ，另下?個(gè)元素進(jìn)?窗?。

O(N^2)

代碼

class Solution 
{
public:int minSubArrayLen(int target, vector<int>& nums) {int res = INT_MAX;int sum = 0;for(int left = 0, right = 0; right < nums.size(); right++){sum += nums[right];//進(jìn)窗口while(sum >= target)//判斷{res = min(res, right - left + 1);//更新結(jié)果sum -= nums[left++];//出窗口}}return res == INT_MAX? 0:res;}};

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

題目

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

解法一（暴力求解）

從每一個(gè)字母開始向后枚舉無重復(fù)字符的字串最大的長度
利用哈希表來統(tǒng)計(jì)每一個(gè)字符出現(xiàn)的次數(shù)

代碼

class Solution 
{
public:int lengthOfLongestSubstring(string s) {int res = 0;int n = s.size();for(int i = 0; i < n; i++){//利用數(shù)組模擬哈希統(tǒng)計(jì)字符出現(xiàn)次數(shù)int hash[128] = {0};for(int j = i; j < n; j++){hash[s[j]]++;//統(tǒng)計(jì)字符的次數(shù)if(hash[s[j]] > 1)//判斷{break;}res = max(res, j - i + 1);}}return res;}
};

解法二（滑動(dòng)窗口）

右端元素 ch 進(jìn)?窗?的時(shí)候，哈希表統(tǒng)計(jì)這個(gè)字符的頻次：

• 如果這個(gè)字符出現(xiàn)的頻次超過 1 ，說明窗?內(nèi)有重復(fù)元素，那么就從左側(cè)開始劃出窗?，
  直到 ch 這個(gè)元素的頻次變?yōu)?1 ，然后再更新結(jié)果。
• 如果沒有超過 1 ，說明當(dāng)前窗?沒有重復(fù)元素，可以直接更新結(jié)果。
  代碼

class Solution 
{
public:int lengthOfLongestSubstring(string s) {int res = 0;int n = s.size();int hash[128] = {0};//利用數(shù)組模擬哈希統(tǒng)計(jì)字符出現(xiàn)次數(shù)for(int left = 0, right = 0; right < n; right++){hash[s[right]]++;//進(jìn)窗口while(hash[s[right]] > 1)//判斷{hash[s[left]]--;//出窗口left++;}res = max(res, right - left + 1);// 更新結(jié)果}return res;}
};

Leetcode1004. 最大連續(xù)1的個(gè)數(shù) III

題目

Leetcode1004. 最大連續(xù)1的個(gè)數(shù) III

解法（滑動(dòng)窗口）

我們發(fā)現(xiàn)一會從左邊開始減、一會從右邊開始減，這樣做起來十分麻煩，因?yàn)槲覀儾淮_定從哪邊開始，所以我們不要想著如何反轉(zhuǎn)，而是一段連續(xù)的1中間有k個(gè)0。
因此，我們將題目轉(zhuǎn)化為了求一段最長連續(xù)區(qū)間，要求其中的0不能超過k

代碼

class Solution 
{
public:int longestOnes(vector<int>& nums, int k) {int res = 0;int zero = 0;//統(tǒng)計(jì)0的個(gè)數(shù)for(int left = 0, right = 0; right < nums.size(); right++){if(nums[right] == 0) zero++;//進(jìn)窗口while(zero > k)//判斷{if(nums[left++] == 0) zero--;//出窗口}res = max(res, right - left + 1);//更新結(jié)果}return res;}
};