目錄

長度最小的子數組

無重復字符的最長子串?

最大連續1的個數

將x減到0的最小操作數

找到字符串中所有字母異位詞

---

長度最小的子數組

sum比target小就進窗口，sum比target大就出窗口，由于數組是正數，所以相加會使sum變大，相減會使sum變小，至于為什么可以這樣做，這其實是在暴力枚舉的基礎上進行了優化，例如2，3，1，2相加等于8已經超過target，這樣就不需要繼續加后面的4，3，因為此時已經滿足條件，我們要做的是在滿足要求的基礎上使len盡量小。?

代碼實現如下：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int sum = 0, len = INT_MAX, n = nums.size();for (int right = 0, left = 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;}
};

---

無重復字符的最長子串?

利用哈希表記錄字符個數，注意本題字符包括數字，字母及空格，意味著我們要開一個128大小的數組。代碼實現如下：

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = { 0 }; // 使用數組來模擬哈希表int n = s.size(), len = 0;for (int left = 0, right = 0; right < n;right++){hash[s[right]]++; // 進窗口while (hash[s[right]] == 2) // 判斷{hash[s[left++]]--; // 出窗口}len = max(len, right - left + 1); // 更新結果}return len;}
};

---

最大連續1的個數

和上題類似，通過滑動窗口，調節0的個數，最關鍵的在于將題目意思轉換為找不超過k個0的子數組，如果超過k就出窗口，未超過就進窗口，代碼實現如下：

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int zero = 0, len = 0; // 計數器for (int left = 0, right = 0; right < nums.size(); right++){if (nums[right] == 0) // 進窗口zero++; // 計數while (zero > k) // 判斷{if (nums[left] == 0)zero--;left++; // 出窗口}len = max(len, right - left + 1);}return len;}
};

---

將x減到0的最小操作數

本題思想為正難則反，如果題目正向思考困難，可以從另外一方面思考，例如本題要找最短長度，且元素可能在左右端口出現，另外最短長度數組元素之和剛好為x，這個代碼實現起來過于麻煩，可以想找一個最長長度的子數組，使他元素之和剛好為sum - x，這樣又轉化為滑動窗口問題。

注意：len不能設置為0，因為有可能整個數組都是構成x的元素，最終判斷是否存在時不能用len == 0 這個判斷式來判斷數組是否存在子數組可以將x減到0，應當設置為-1。另外，該題只有在sum2 == target時才能更新結果，否則不更新。代碼如下：

class Solution {
public:int minOperations(vector<int>& nums, int x) {// 記算整個數組的和int sum1 = 0, n = nums.size();for (auto e : nums){sum1 += e;}// 找出最長子數組的和 sum1 - xint target = sum1 - x, len = -1, sum2 = 0;// 處理細節問題if (target < 0)return -1;// 滑動窗口解決問題for (int left = 0, right = 0; right < n; right++){sum2 += nums[right]; // 進窗口while (sum2 > target) // 判斷sum2 -= nums[left++]; // 出窗口if (sum2 == target)len = max(len, right - left + 1); // 更新結果}if (len == -1)return len;elsereturn n - len;}
};

---

找到字符串中所有字母異位詞

在更新結果時不需要遍歷兩個哈希表，通過count計數器來判斷hash2里的有效個數是否和m相等即可，代碼實現如下：

class Solution {
public:vector<int> findAnagrams(string s, string p) {int hash1[26] = { 0 }, hash2[26] = { 0 }, n = s.size(), m = p.size();// 統計 p 的每個字符出現的次數for (auto e : p)hash1[e - 'a']++;vector<int> ret;// 統計 s 的每個字符出現的次數for (int left = 0, right = 0,count = 0; right < n; right++){char in = s[right];if (++hash2[in - 'a'] <= hash1[in - 'a']) // 進窗口 + 維護 countcount++;if (right - left + 1 > m) // 判斷{char out = s[left++];if (hash2[out - 'a']-- <= hash1[out - 'a']) // 出窗口 + 維護 countcount--;}// 更新結果if (count == m)ret.push_back(left);}return ret;}
};