[力扣刷题总结](双指针篇)
文章目錄
- |||||||||||||||||||| 雙指針 ||||||||||||||||||
- 905. 按奇偶排序數(shù)組
- 解法1：雙指針+原地交換
- 解法2：兩次遍歷+保持相對位置
- 475. 供暖器
- 解法1：雙指針+貪心
- 202. 快樂數(shù)
- 解法1：快慢指針
- 相似題目：141. 環(huán)形鏈表
- 解法1：快慢指針
- 相似題目：142. 環(huán)形鏈表 II
- 解法1：快慢指針
- 解法2：哈希表
- 相似題目：287. 尋找重復(fù)數(shù)
- 解法1：快慢指針
- 解法2：二分查找
- 15. 三數(shù)之和
- 解法1：雙指針
- 相似題目：611. 有效三角形的個數(shù)
- 解法1：雙指針
- 相似題目：16. 最接近的三數(shù)之和
- 解法1：雙指針+排序
- 相似題目：1. 兩數(shù)之和
- 解法1：哈希表
- 31. 下一個排列
- 解法1：兩遍掃描+雙指針
- 165. 比較版本號
- 解法1：雙指針
- 75. 顏色分類
- 解法1：雙指針+一次遍歷
- 解法2：雙指針+一次遍歷
- ~~縮減搜索空間的思想~~
- 11. 盛最多水的容器
- 解法1：雙指針
- 240. 搜索二維矩陣 II
- 解法1：雙指針+二叉搜索樹
- 167. 兩數(shù)之和 II - 輸入有序數(shù)組
- 解法1：雙指針
- |||||||||||||||| 滑動窗口 ||||||||||||||||||
- 992. K 個不同整數(shù)的子數(shù)組
- 解法1：雙指針（滑動窗口）
- 相似題目：904. 水果成籃
- 解法1：雙指針（滑動窗口）
- 相似題目：76. 最小覆蓋子串
- 解法1：滑動窗口
- 3. 無重復(fù)字符的最長子串
- 解法1：滑動窗口+哈希
- 424. 替換后的最長重復(fù)字符
- 解法1：滑動窗口
- 相似題目：485. 最大連續(xù) 1 的個數(shù)
- 解法1：數(shù)組+一次遍歷
- 劍指 Offer 59 - I. 滑動窗口的最大值
- 解法1：滑動窗口+單調(diào)隊列+雙向隊列
- 解法2：優(yōu)先隊列+滑動窗口
- 相似題目：劍指 Offer 59 - II. 隊列的最大值
- 解法1：單調(diào)隊列+滑動窗口
- 1052. 愛生氣的書店老板
- 解法1：數(shù)組+滑動窗口
- 209. 長度最小的子數(shù)組
- 解法1：滑動窗口
- 相似題目：718. 最長重復(fù)子數(shù)組
- 解法1：動態(tài)規(guī)劃
- 567. 字符串的排列
- 解法1:滑動窗口
|||||||||||||||||||| 雙指針 ||||||||||||||||||
905. 按奇偶排序數(shù)組
力扣鏈接
給你一個整數(shù)數(shù)組 nums，將 nums 中的的所有偶數(shù)元素移動到數(shù)組的前面，后跟所有奇數(shù)元素。
返回滿足此條件的 任一數(shù)組 作為答案。
示例 1：
輸入：nums = [3,1,2,4]
輸出：[2,4,3,1]
解釋：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也會被視作正確答案。
示例 2：
輸入：nums = [0]
輸出：[0]
提示：
1 <= nums.length <= 5000
0 <= nums[i] <= 5000
解法1：雙指針+原地交換
class Solution { public:vector<int> sortArrayByParity(vector<int>& nums) {int left = 0, right = nums.size() - 1;while (left < right) {while (left < right and nums[left] % 2 == 0) {left++;}while (left < right and nums[right] % 2 == 1) {right--;}if (left < right) {swap(nums[left++], nums[right--]);}}return nums;} };解法2：兩次遍歷+保持相對位置
class Solution { public:vector<int> sortArrayByParity(vector<int>& nums) {vector<int> res;for (auto & num : nums) {if (num % 2 == 0) {res.push_back(num);}}for (auto & num : nums) {if (num % 2 == 1) {res.push_back(num);}}return res;} };475. 供暖器
力扣鏈接
冬季已經(jīng)來臨。 你的任務(wù)是設(shè)計一個有固定加熱半徑的供暖器向所有房屋供暖。
在加熱器的加熱半徑范圍內(nèi)的每個房屋都可以獲得供暖。
現(xiàn)在，給出位于一條水平線上的房屋 houses 和供暖器 heaters 的位置，請你找出并返回可以覆蓋所有房屋的最小加熱半徑。
說明：所有供暖器都遵循你的半徑標(biāo)準(zhǔn)，加熱的半徑也一樣。
示例 1:
輸入: houses = [1,2,3], heaters = [2]
輸出: 1
解釋: 僅在位置2上有一個供暖器。如果我們將加熱半徑設(shè)為1，那么所有房屋就都能得到供暖。
示例 2:
輸入: houses = [1,2,3,4], heaters = [1,4]
輸出: 1
解釋: 在位置1, 4上有兩個供暖器。我們需要將加熱半徑設(shè)為1，這樣所有房屋就都能得到供暖。
示例 3：
輸入：houses = [1,5], heaters = [2]
輸出：3
提示：
1 <= houses.length, heaters.length <= 3 * 104
1 <= houses[i], heaters[i] <= 109
解法1：雙指針+貪心
思路：
這是一道很好的貪心+雙指針的應(yīng)用題。
我們需要保證每個房屋至少在一個加熱器的供暖范圍內(nèi)，那為了讓加熱半徑最小，我們只需要保證每個房屋最近的加熱器的距離小于加熱半徑。
那全局最低的加熱半徑；自然也就等于所有房屋到最近加熱器的距離中的最大值。 這是一個min(max)的問題。
怎么求呢？
如果我們的房屋和加熱器都是按照橫坐標(biāo)排序的；那顯然，我們只需要順次對每個房子找和他相鄰的前后兩個加熱器即可。
用兩個指針分別標(biāo)記房屋和加熱器；不斷移動加熱器，直至加熱器的橫坐標(biāo)大于房屋橫坐標(biāo)。 則當(dāng)前加熱器指針 cur 和 cur-1 就是房屋左邊的加熱器和右邊的加熱器。
我們求兩者到房屋距離中的較小值，就是該房屋最近的加熱器到房屋的距離。
遍歷所有的房屋，取最大值即可。
代碼：
class Solution { public:int findRadius(vector<int>& houses, vector<int>& heaters) {int result = 0;sort(heaters.begin(),heaters.end());sort(houses.begin(),houses.end());int cur = 0;for(int i = 0;i<houses.size();i++){int curDis = abs(houses[i]-heaters[cur]);while(cur < heaters.size()-1 && abs(houses[i]-heaters[cur+1]) <= curDis){curDis = min(abs(houses[i]-heaters[cur+1]),curDis);cur++;}result = max(result,curDis);}return result;} };202. 快樂數(shù)
力扣鏈接
編寫一個算法來判斷一個數(shù) n 是不是快樂數(shù)。
「快樂數(shù)」定義為：
對于一個正整數(shù)，每一次將該數(shù)替換為它每個位置上的數(shù)字的平方和。
然后重復(fù)這個過程直到這個數(shù)變?yōu)?1，也可能是 無限循環(huán) 但始終變不到 1。
如果 可以變?yōu)?1，那么這個數(shù)就是快樂數(shù)。
如果 n 是快樂數(shù)就返回 true ；不是，則返回 false 。
示例 1：
輸入：n = 19
輸出：true
解釋：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
輸入：n = 2
輸出：false
提示：
1 <= n <= 231 - 1
解法1：快慢指針
思路：
（1）使用 “快慢指針” 思想，找出循環(huán)：“快指針” 每次走兩步，“慢指針” 每次走一步，當(dāng)二者相等時，即為一個循環(huán)周期。此時，判斷是不是因為 1 引起的循環(huán)，是的話就是快樂數(shù)，否則不是快樂數(shù)。
（2）這個算法是兩個奔跑選手，一個跑的快，一個跑得慢。在龜兔賽跑的寓言中，跑的慢的稱為 “烏龜”，跑得快的稱為 “兔子”。
不管烏龜和兔子在循環(huán)中從哪里開始，它們最終都會相遇。這是因為兔子每走一步就向烏龜靠近一個節(jié)點（在它們的移動方向上）。
（3）注意：此題不建議用集合記錄每次的計算結(jié)果來判斷是否進(jìn)入循環(huán)，因為這個集合可能大到無法存儲；另外，也不建議使用遞歸，同理，如果遞歸層次較深，會直接導(dǎo)致調(diào)用棧崩潰。不要因為這個題目給出的整數(shù)是 int 型而投機(jī)取巧。
代碼：
class Solution { public:int get_next(int n){int sum = 0;while(n>0){sum += (n%10)*(n%10);n /= 10;}return sum;}bool isHappy(int n) {int slow = n, fast = n;do{slow = get_next(slow);fast = get_next(fast);fast = get_next(fast);} while(slow != fast);//判斷是否有循環(huán)return slow == 1;} };相似題目：141. 環(huán)形鏈表
力扣鏈接
給你一個鏈表的頭節(jié)點 head ，判斷鏈表中是否有環(huán)。
如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意：pos 不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識鏈表的實際情況。
如果鏈表中存在環(huán)，則返回 true 。 否則，返回 false 。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。
示例 2：
輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。
示例 3：
輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環(huán)。
提示：
鏈表中節(jié)點的數(shù)目范圍是 [0, 104]
-105 <= Node.val <= 105
pos 為 -1 或者鏈表中的一個 有效索引 。
進(jìn)階：你能用 O(1)（即，常量）內(nèi)存解決此問題嗎？
解法1：快慢指針
參考
思路：
**當(dāng)一個鏈表有環(huán)時，快慢指針都會陷入環(huán)中進(jìn)行無限次移動，然后變成了追及問題。**想象一下在操場跑步的場景，只要一直跑下去，快的總會追上慢的。當(dāng)兩個指針都進(jìn)入環(huán)后，每輪移動使得慢指針到快指針的距離增加一，同時快指針到慢指針的距離也減少一，只要一直移動下去，快指針總會追上慢指針。
代碼：
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:bool hasCycle(ListNode *head) {ListNode* slow = head, *fast = head;while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;if (fast == slow) return true;}return false;} };復(fù)雜度分析：
時間復(fù)雜度：O(N)，其中 N 是鏈表中的節(jié)點數(shù)。
當(dāng)鏈表中不存在環(huán)時，快指針將先于慢指針到達(dá)鏈表尾部，鏈表中每個節(jié)點至多被訪問兩次。
當(dāng)鏈表中存在環(huán)時，每一輪移動后，快慢指針的距離將減小一。而初始距離為環(huán)的長度，因此至多移動 N輪。
空間復(fù)雜度：O(1)。我們只使用了兩個指針的額外空間。
相似題目：142. 環(huán)形鏈表 II
力扣鏈接
給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null。
如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意：pos 不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識鏈表的實際情況。
不允許修改 鏈表。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節(jié)點
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。
示例 2：
輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節(jié)點
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。
示例 3：
輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環(huán)。
提示：
鏈表中節(jié)點的數(shù)目范圍在范圍 [0, 104] 內(nèi)
-105 <= Node.val <= 105
pos 的值為 -1 或者鏈表中的一個有效索引
進(jìn)階：你是否可以使用 O(1) 空間解決此題？
解法1：快慢指針
思路：
這道題目，不僅考察對鏈表的操作，而且還需要一些數(shù)學(xué)運(yùn)算。
主要考察兩知識點：
1.判斷鏈表是否環(huán) 2.如果有環(huán)，如何找到這個環(huán)的入口（1）
（3）
代碼：
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head, *slow = head;while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;if(slow == fast){ListNode* index = head;while(index != slow){index = index->next;slow = slow->next;}return index;}}return NULL;} };復(fù)雜度分析：
時間復(fù)雜度：O(N)，其中 N 為鏈表中節(jié)點的數(shù)目。在最初判斷快慢指針是否相遇時，slow 指針走過的距離不會超過鏈表的總長度；隨后尋找入環(huán)點時，走過的距離也不會超過鏈表的總長度。因此，總的執(zhí)行時間為 O(N)+O(N)=O(N)。
空間復(fù)雜度：O(1)。我們只使用了slow,fast,ptr 三個指針。
解法2：哈希表
思路：
一個非常直觀的思路是：我們遍歷鏈表中的每個節(jié)點，并將它記錄下來；一旦遇到了此前遍歷過的節(jié)點，就可以判定鏈表中存在環(huán)。借助哈希表可以很方便地實現(xiàn)。
代碼：
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode *detectCycle(ListNode *head) {unordered_map<ListNode*,int> umap;ListNode* ptr = head;while(ptr!=NULL){if(umap[ptr] > 1) return ptr;umap[ptr]++;ptr = ptr->next;}return NULL;} };復(fù)雜度分析：
時間復(fù)雜度：O(N)，其中 N 為鏈表中節(jié)點的數(shù)目。我們恰好需要訪問鏈表中的每一個節(jié)點。
空間復(fù)雜度：O(N)，其中 N 為鏈表中節(jié)點的數(shù)目。我們需要將鏈表中的每個節(jié)點都保存在哈希表當(dāng)中。
相似題目：287. 尋找重復(fù)數(shù)
力扣鏈接
給定一個包含 n + 1 個整數(shù)的數(shù)組 nums ，其數(shù)字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重復(fù)的整數(shù)。
假設(shè) nums 只有 一個重復(fù)的整數(shù) ，找出 這個重復(fù)的數(shù) 。
你設(shè)計的解決方案必須不修改數(shù)組 nums 且只用常量級 O(1) 的額外空間。
示例 1：
輸入：nums = [1,3,4,2,2]
輸出：2
示例 2：
輸入：nums = [3,1,3,4,2]
輸出：3
示例 3：
輸入：nums = [1,1]
輸出：1
示例 4：
輸入：nums = [1,1,2]
輸出：1
提示：
1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一個整數(shù) 出現(xiàn) 兩次或多次 ，其余整數(shù)均只出現(xiàn) 一次
進(jìn)階：
如何證明 nums 中至少存在一個重復(fù)的數(shù)字?
你可以設(shè)計一個線性級時間復(fù)雜度 O(n) 的解決方案嗎？
解法1：快慢指針
思路：
代碼：
class Solution { public:int findDuplicate(vector<int>& nums) {//快慢指針int slow = 0, fast = 0;while(true){slow = nums[slow];fast = nums[nums[fast]];if(slow == fast){fast = 0;while(nums[slow] != nums[fast]){fast = nums[fast];slow = nums[slow];}return nums[slow];}}} };復(fù)雜度分析：
時間復(fù)雜度：O(n)?！窮loyd 判圈算法」時間復(fù)雜度為線性的時間復(fù)雜度。
空間復(fù)雜度：O(1)。我們只需要常數(shù)空間存放若干變量。
解法2：二分查找
思路：
找到不正常（nums中值為該下標(biāo)的數(shù)重復(fù)）的那個數(shù)組下標(biāo)
代碼：
class Solution { public:int findDuplicate(vector<int>& nums) {int left = 0, right = nums.size() - 1;while(left < right){// 猜測中間點數(shù)重復(fù)，查找小于等于該中間數(shù)的個數(shù)，如果等于該中間數(shù)說明沒有重復(fù)，區(qū)間上移動，否則該區(qū)間有重復(fù)數(shù)int mid = left + (right - left)/2;int count = 0;for(auto& num:nums){if(num<=mid) count++;}// 如果小于等于該數(shù)的值的數(shù)量等于該數(shù)，則向上滑動區(qū)間if(count<=mid){left = mid + 1;}else{right = mid;}}return left;} };復(fù)雜度分析：
時間復(fù)雜度：O(nlogn)，其中 n 為 nums 數(shù)組的長度。二分查找最多需要二分 O(logn) 次，每次判斷的時候需要O(n) 遍歷nums 數(shù)組求解小于等于 mid 的數(shù)的個數(shù)，因此總時間復(fù)雜度為 O(nlogn)。
空間復(fù)雜度：O(1)。我們只需要常數(shù)空間存放若干變量。
15. 三數(shù)之和
力扣鏈接
給你一個包含 n 個整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有和為 0 且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組。
示例 1：
輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
示例 2：
輸入：nums = []
輸出：[]
示例 3：
輸入：nums = [0]
輸出：[]
提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
解法1：雙指針
思路：
（1）這道題目使用哈希法并不十分合適，因為在去重的操作中有很多細(xì)節(jié)需要注意，在面試中很難直接寫出沒有bug的代碼。
而且使用哈希法 在使用兩層for循環(huán)的時候，能做的剪枝操作很有限，雖然時間復(fù)雜度是O(n2)O(n^2)O(n2)，也是可以在leetcode上通過，但是程序的執(zhí)行時間依然比較長 。
（2）接下來我來介紹另一個解法：雙指針法，這道題目使用雙指針法 要比哈希法高效一些，那么來講解一下具體實現(xiàn)的思路。
拿這個nums數(shù)組來舉例，首先將數(shù)組排序，然后有一層for循環(huán)，i從下標(biāo)0的地方開始，同時定一個下標(biāo)left 定義在i+1的位置上，定義下標(biāo)right 在數(shù)組結(jié)尾的位置上。
依然還是在數(shù)組中找到 abc 使得a + b +c =0，我們這里相當(dāng)于 a = nums[i] b = nums[left] c = nums[right]。
接下來如何移動left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就說明 此時三數(shù)之和大了，因為數(shù)組是排序后了，所以right下標(biāo)就應(yīng)該向左移動，這樣才能讓三數(shù)之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 說明 此時 三數(shù)之和小了，left 就向右移動，才能讓三數(shù)之和大一些，直到left與right相遇為止。
代碼：
class Solution { public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;sort(nums.begin(),nums.end());for(int i = 0;i<nums.size();i++){if(nums[i] > 0) return result;//去重if(i>0 && nums[i] == nums[i-1] ) continue;int left = i+1;int right = nums.size() - 1;while(right > left){if(nums[i] + nums[left] + nums[right] < 0) left++;else if(nums[i] + nums[left] + nums[right] > 0) right--;else{result.push_back(vector<int>{nums[i],nums[left],nums[right]}); 去重邏輯應(yīng)該放在找到一個三元組之后while(right>left && nums[right] == nums[right-1]) right--;while(right>left && nums[left] == nums[left+1]) left++;right--;left++;}}}return result;} };復(fù)雜度分析：
時間復(fù)雜度：O(n2)O(n^2)O(n2)。
相似題目：611. 有效三角形的個數(shù)
力扣鏈接
給定一個包含非負(fù)整數(shù)的數(shù)組 nums ，返回其中可以組成三角形三條邊的三元組個數(shù)。
示例 1:
輸入: nums = [2,2,3,4]
輸出: 3
解釋:有效的組合是:
2,3,4 (使用第一個 2)
2,3,4 (使用第二個 2)
2,2,3
示例 2:
輸入: nums = [4,2,3,4]
輸出: 4
提示:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
解法1：雙指針
class Solution { public:int triangleNumber(vector<int>& nums) {int res = 0;int n = nums.size();sort(nums.begin(),nums.end());for(int i = n-1;i>=2;i--){int left = 0, right = i-1;while(left < right){if(nums[left] + nums[right] > nums[i]){res+= right - left;//i, r 和從l到r-1都可組成三角形，個數(shù)為 (r-1) - l + 1 = r - lright--;}else{left++;}}}return res;} };相似題目：16. 最接近的三數(shù)之和
力扣鏈接
給你一個長度為 n 的整數(shù)數(shù)組 nums 和 一個目標(biāo)值 target。請你從 nums 中選出三個整數(shù)，使它們的和與 target 最接近。
返回這三個數(shù)的和。
假定每組輸入只存在恰好一個解。
示例 1：
輸入：nums = [-1,2,1,-4], target = 1
輸出：2
解釋：與 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：
輸入：nums = [0,0,0], target = 1
輸出：0
提示：
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
解法1：雙指針+排序
class Solution { public:int threeSumClosest(vector<int>& nums, int target) {sort(nums.begin(),nums.end());int n = nums.size();int clostSum = nums[0] + nums[1] + nums[2];for(int i = 0;i<n-2;i++){if(i > 0 && nums[i-1] == nums[i]) continue;int left = i+1, right = n - 1;while(left<right){int threeSum = nums[i] + nums[left] + nums[right];if(abs(threeSum-target)<abs(clostSum-target)){clostSum = threeSum;}if(threeSum > target){right--;while(left < right && nums[right] == nums[right+1]){right--;}}else if(threeSum < target){left++;while(left < right && nums[left] == nums[left-1]){left++;}}else return target;}}return clostSum;} };相似題目：1. 兩數(shù)之和
力扣鏈接
給定一個整數(shù)數(shù)組 nums 和一個整數(shù)目標(biāo)值 target，請你在該數(shù)組中找出 和為目標(biāo)值 target 的那 兩個 整數(shù)，并返回它們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，數(shù)組中同一個元素在答案里不能重復(fù)出現(xiàn)。
你可以按任意順序返回答案。
示例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
輸入：nums = [3,2,4], target = 6
輸出：[1,2]
示例 3：
輸入：nums = [3,3], target = 6
輸出：[0,1]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只會存在一個有效答案
進(jìn)階：你可以想出一個時間復(fù)雜度小于 O(n2) 的算法嗎？
解法1：哈希表
思路：
代碼：
class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> umap;for(int i = 0;i<nums.size();i++){auto iter = umap.find(target-nums[i]);if(iter != umap.end()) return {iter->second,i};umap.insert(pair<int,int>(nums[i],i));}return {};} }; class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> umap;//target-i ifor(int i = 0;i<nums.size();i++){umap[target-nums[i]] = i;}vector<int> result;for(int i = 0;i<nums.size();i++){if(umap.count(nums[i]) > 0 && umap[nums[i]] != i) {result.push_back(i);result.push_back(umap[nums[i]]);break;}}return result;} };31. 下一個排列
likou
整數(shù)數(shù)組的一個 排列 就是將其所有成員以序列或線性順序排列。
例如，arr = [1,2,3] ，以下這些都可以視作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整數(shù)數(shù)組的 下一個排列 是指其整數(shù)的下一個字典序更大的排列。更正式地，如果數(shù)組的所有排列根據(jù)其字典順序從小到大排列在一個容器中，那么數(shù)組的 下一個排列 就是在這個有序容器中排在它后面的那個排列。如果不存在下一個更大的排列，那么這個數(shù)組必須重排為字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一個排列是 [1,3,2] 。
類似地，arr = [2,3,1] 的下一個排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一個排列是 [1,2,3] ，因為 [3,2,1] 不存在一個字典序更大的排列。
給你一個整數(shù)數(shù)組 nums ，找出 nums 的下一個排列。
必須 原地 修改，只允許使用額外常數(shù)空間。
示例 1：
輸入：nums = [1,2,3]
輸出：[1,3,2]
示例 2：
輸入：nums = [3,2,1]
輸出：[1,2,3]
示例 3：
輸入：nums = [1,1,5]
輸出：[1,5,1]
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100
解法1：兩遍掃描+雙指針
思路：
代碼：
class Solution { public:void nextPermutation(vector<int>& nums) {int i = nums.size() - 2;while(i >= 0 && nums[i+1] <= nums[i]) i--;int firstIndex = i;if(firstIndex >= 0){int j = nums.size() - 1;while(nums[j] <= nums[firstIndex]) j--;int secondIndex = j;swap(nums[firstIndex],nums[secondIndex]);}reverse(nums.begin()+firstIndex+1,nums.end());} };165. 比較版本號
力扣鏈接
給你兩個版本號 version1 和 version2 ，請你比較它們。
版本號由一個或多個修訂號組成，各修訂號由一個 ‘.’ 連接。每個修訂號由 多位數(shù)字 組成，可能包含 前導(dǎo)零 。每個版本號至少包含一個字符。修訂號從左到右編號，下標(biāo)從 0 開始，最左邊的修訂號下標(biāo)為 0 ，下一個修訂號下標(biāo)為 1 ，以此類推。例如，2.5.33 和 0.1 都是有效的版本號。
比較版本號時，請按從左到右的順序依次比較它們的修訂號。比較修訂號時，只需比較 忽略任何前導(dǎo)零后的整數(shù)值 。也就是說，修訂號 1 和修訂號 001 相等 。如果版本號沒有指定某個下標(biāo)處的修訂號，則該修訂號視為 0 。例如，版本 1.0 小于版本 1.1 ，因為它們下標(biāo)為 0 的修訂號相同，而下標(biāo)為 1 的修訂號分別為 0 和 1 ，0 < 1 。
返回規(guī)則如下：
如果 version1 > version2 返回 1，
如果 version1 < version2 返回 -1，
除此之外返回 0。
示例 1：
輸入：version1 = “1.01”, version2 = “1.001”
輸出：0
解釋：忽略前導(dǎo)零，“01” 和 “001” 都表示相同的整數(shù) “1”
示例 2：
輸入：version1 = “1.0”, version2 = “1.0.0”
輸出：0
解釋：version1 沒有指定下標(biāo)為 2 的修訂號，即視為 “0”
示例 3：
輸入：version1 = “0.1”, version2 = “1.1”
輸出：-1
解釋：version1 中下標(biāo)為 0 的修訂號是 “0”，version2 中下標(biāo)為 0 的修訂號是 “1” 。0 < 1，所以 version1 < version2
提示：
1 <= version1.length, version2.length <= 500
version1 和 version2 僅包含數(shù)字和 ‘.’
version1 和 version2 都是 有效版本號
version1 和 version2 的所有修訂號都可以存儲在 32 位整數(shù) 中
解法1：雙指針
class Solution { public:int compareVersion(string version1, string version2) {int i = 0, j = 0;int m = version1.size(), n = version2.size();while(i < m || j < n){long a = 0, b = 0;while(i < m && version1[i] != '.') a = a*10 + version1[i++] - '0';while(j < n && version2[j] != '.') b = b*10 + version2[j++] - '0';if(a > b) return 1;else if(a < b) return -1;i++;j++;}return 0;} };75. 顏色分類
力扣鏈接
給定一個包含紅色、白色和藍(lán)色、共 n 個元素的數(shù)組 nums ，原地對它們進(jìn)行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍(lán)色順序排列。
我們使用整數(shù) 0、 1 和 2 分別表示紅色、白色和藍(lán)色。
必須在不使用庫的sort函數(shù)的情況下解決這個問題。
示例 1：
輸入：nums = [2,0,2,1,1,0]
輸出：[0,0,1,1,2,2]
示例 2：
輸入：nums = [2,0,1]
輸出：[0,1,2]
提示：
n == nums.length
1 <= n <= 300
nums[i] 為 0、1 或 2
進(jìn)階：
你可以不使用代碼庫中的排序函數(shù)來解決這道題嗎？
你能想出一個僅使用常數(shù)空間的一趟掃描算法嗎？
解法1：雙指針+一次遍歷
思路：
0，1，2 排序。一次遍歷，如果是0，則移動到表頭，如果是2，則移動到表尾，不用考慮1。0和2處理完，1還會有錯嗎？
代碼：
class Solution { public:void sortColors(vector<int>& nums) {//雙指針 一次遍歷int p0 = 0, p2 = nums.size() - 1;for(int i = 0;i<=p2;i++){while(i <= p2 && nums[i] == 2){swap(nums[i],nums[p2]);p2--;}if(nums[i] == 0){swap(nums[i],nums[p0]);p0++;}}} };解法2：雙指針+一次遍歷
class Solution { public:void sortColors(vector<int>& nums) {//雙指針 一次遍歷int p0 = 0, p1 = 0;for(int i = 0;i<nums.size();i++){if(nums[i] == 1){swap(nums[i],nums[p1]);p1++;}if(nums[i] == 0){swap(nums[i],nums[p0]);if(p0 < p1){//這個時候的nums[i]有可能是1swap(nums[i],nums[p1]);}p0++;p1++;}}} };縮減搜索空間的思想
11. 盛最多水的容器
力扣鏈接
給你 n 個非負(fù)整數(shù) a1，a2，…，an，每個數(shù)代表坐標(biāo)中的一個點 (i, ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0) 。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
說明：你不能傾斜容器。
示例 1：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解釋：圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49。
示例 2：
輸入：height = [1,1]
輸出：1
示例 3：
輸入：height = [4,3,2,1,4]
輸出：16
示例 4：
輸入：height = [1,2,1]
輸出：2
提示：
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
解法1：雙指針
思路：
代碼：
復(fù)雜度分析：
時間復(fù)雜度 O(N)? ： 雙指針遍歷一次底邊寬度 N?? 。
空間復(fù)雜度 O(1) ： 變量 i , j , res 使用常數(shù)額外空間。
240. 搜索二維矩陣 II
力扣鏈接
編寫一個高效的算法來搜索 m x n 矩陣 matrix 中的一個目標(biāo)值 target 。該矩陣具有以下特性：
示例 1：
輸入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
輸出：true
示例 2：
輸入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
輸出：false
提示：
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrix[i][j] <= 109
每行的所有元素從左到右升序排列
每列的所有元素從上到下升序排列
-109 <= target <= 109
解法1：雙指針+二叉搜索樹
思路：
該做法則與 （題解）74. 搜索二維矩陣 的「解法二」完全一致。
我們可以將二維矩陣抽象成「以右上角為根的 BST」：
那么我們可以從根（右上角）開始搜索，如果當(dāng)前的節(jié)點不等于目標(biāo)值，可以按照樹的搜索順序進(jìn)行：
當(dāng)前節(jié)點「大于」目標(biāo)值，搜索當(dāng)前節(jié)點的「左子樹」，也就是當(dāng)前矩陣位置的「左方格子」，即 c–
當(dāng)前節(jié)點「小于」目標(biāo)值，搜索當(dāng)前節(jié)點的「右子樹」，也就是當(dāng)前矩陣位置的「下方格子」，即 r++
代碼：
class Solution { public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = matrix[0].size();int row = 0, col = n -1;while(row<m && col >=0){if(matrix[row][col] < target) row++;else if(matrix[row][col] > target) col--;else return true;}return false;} };復(fù)雜度分析：
時間復(fù)雜度：O(m + n)
空間復(fù)雜度：O(1)
167. 兩數(shù)之和 II - 輸入有序數(shù)組
力扣鏈接
給定一個已按照 非遞減順序排列 的整數(shù)數(shù)組 numbers ，請你從數(shù)組中找出兩個數(shù)滿足相加之和等于目標(biāo)數(shù) target 。
函數(shù)應(yīng)該以長度為 2 的整數(shù)數(shù)組的形式返回這兩個數(shù)的下標(biāo)值。numbers 的下標(biāo) 從 1 開始計數(shù) ，所以答案數(shù)組應(yīng)當(dāng)滿足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假設(shè)每個輸入 只對應(yīng)唯一的答案 ，而且你 不可以 重復(fù)使用相同的元素。
示例 1：
輸入：numbers = [2,7,11,15], target = 9
輸出：[1,2]
解釋：2 與 7 之和等于目標(biāo)數(shù) 9 。因此 index1 = 1, index2 = 2 。
示例 2：
輸入：numbers = [2,3,4], target = 6
輸出：[1,3]
示例 3：
輸入：numbers = [-1,0], target = -1
輸出：[1,2]
提示：
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 非遞減順序 排列
-1000 <= target <= 100
解法1：雙指針
思路：
代碼：
class Solution { public:vector<int> twoSum(vector<int>& numbers, int target) {vector<int> result;int right = numbers.size() -1;for(int i = 0;i<numbers.size();i++){if(numbers[i] > target) return result;while(numbers[right] + numbers[i] > target) right--;if (numbers[right] + numbers[i] == target){result.push_back(i+1);result.push_back(right+1);return result;}}return result;} };|||||||||||||||| 滑動窗口 ||||||||||||||||||
992. K 個不同整數(shù)的子數(shù)組
力扣鏈接
給定一個正整數(shù)數(shù)組 A，如果 A 的某個子數(shù)組中不同整數(shù)的個數(shù)恰好為 K，則稱 A 的這個連續(xù)、不一定不同的子數(shù)組為好子數(shù)組。
（例如，[1,2,3,1,2] 中有 3 個不同的整數(shù)：1，2，以及 3。）
返回 A 中好子數(shù)組的數(shù)目。
示例 1：
輸入：A = [1,2,1,2,3], K = 2
輸出：7
解釋：恰好由 2 個不同整數(shù)組成的子數(shù)組：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
示例 2：
輸入：A = [1,2,1,3,4], K = 3
輸出：3
解釋：恰好由 3 個不同整數(shù)組成的子數(shù)組：[1,2,1,3], [2,1,3], [1,3,4].
提示：
1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length
解法1：雙指針（滑動窗口）
思路：
（1）
（2）實現(xiàn)函數(shù) atMostWithKDistinct(A, K) ，表示**「最多存在 KK 個不同整數(shù)的子區(qū)間的個數(shù)」**。于是 atMostWithKDistinct(A, K) - atMostWithKDistinct(A, K - 1) 即為所求。
代碼：
class Solution { public:int mostDistanct(vector<int>& nums, int k){unordered_map<int,int> umap;int left = 0, right = 0, result = 0;while(right < nums.size()){// [left, right) umap[nums[right]]++;right++;while(umap.size() > k){umap[nums[left]]--;if(umap[nums[left]] == 0) umap.erase(nums[left]);left++;}result += right - left;}return result;}int subarraysWithKDistinct(vector<int>& nums, int k) {return mostDistanct(nums, k) - mostDistanct(nums, k - 1);} };為什么可以用新子數(shù)組的長度即 【right - left】來表示增加的子數(shù)組個數(shù)呢？
可以借鑒動態(tài)規(guī)劃的思想，舉個例子就好理解了：
當(dāng)滿足條件的子數(shù)組從 [A,B,C] 增加到 [A,B,C,D] 時，新子數(shù)組的長度為 4，同時增加的子數(shù)組為 [D], [C,D], [B,C,D], [A,B,C,D] 也為4。
復(fù)雜度分析：
時間復(fù)雜度：O(n)，其中 n是數(shù)組長度。我們至多只需要遍歷該數(shù)組2次（右指針和左指針各一次）。
空間復(fù)雜度：O(n)，其中 n是數(shù)組長度。我們需要記錄每一個數(shù)的出現(xiàn)次數(shù)，本題中數(shù)的大小不超過數(shù)組長度。
相似題目：904. 水果成籃
力扣鏈接
你正在探訪一家農(nóng)場，農(nóng)場從左到右種植了一排果樹。這些樹用一個整數(shù)數(shù)組 fruits 表示，其中 fruits[i] 是第 i 棵樹上的水果 種類 。
你想要盡可能多地收集水果。然而，農(nóng)場的主人設(shè)定了一些嚴(yán)格的規(guī)矩，你必須按照要求采摘水果：
你只有 兩個 籃子，并且每個籃子只能裝 單一類型 的水果。每個籃子能夠裝的水果總量沒有限制。
你可以選擇任意一棵樹開始采摘，你必須從 每棵 樹（包括開始采摘的樹）上 恰好摘一個水果 。采摘的水果應(yīng)當(dāng)符合籃子中的水果類型。每采摘一次，你將會向右移動到下一棵樹，并繼續(xù)采摘。
一旦你走到某棵樹前，但水果不符合籃子的水果類型，那么就必須停止采摘。
給你一個整數(shù)數(shù)組 fruits ，返回你可以收集的水果的 最大 數(shù)目。
示例 1：
輸入：fruits = [1,2,1]
輸出：3
解釋：可以采摘全部 3 棵樹。
示例 2：
輸入：fruits = [0,1,2,2]
輸出：3
解釋：可以采摘 [1,2,2] 這三棵樹。
如果從第一棵樹開始采摘，則只能采摘 [0,1] 這兩棵樹。
示例 3：
輸入：fruits = [1,2,3,2,2]
輸出：4
解釋：可以采摘 [2,3,2,2] 這四棵樹。
如果從第一棵樹開始采摘，則只能采摘 [1,2] 這兩棵樹。
示例 4：
輸入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
輸出：5
解釋：可以采摘 [1,2,1,1,2] 這五棵樹。
提示：
1 <= fruits.length <= 105
0 <= fruits[i] < fruits.length
解法1：雙指針（滑動窗口）
思路：
代碼：
復(fù)雜度分析：
時間復(fù)雜度：O(N)，其中 N 是 tree 的長度。
空間復(fù)雜度：O(N)。
相似題目：76. 最小覆蓋子串
力扣鏈接
給你一個字符串 s 、一個字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 “” 。
注意：
對于 t 中重復(fù)字符，我們尋找的子字符串中該字符數(shù)量必須不少于 t 中該字符數(shù)量。
如果 s 中存在這樣的子串，我們保證它是唯一的答案。
示例 1：
輸入：s = “ADOBECODEBANC”, t = “ABC”
輸出：“BANC”
示例 2：
輸入：s = “a”, t = “a”
輸出：“a”
示例 3:
輸入: s = “a”, t = “aa”
輸出: “”
解釋: t 中兩個字符 ‘a(chǎn)’ 均應(yīng)包含在 s 的子串中，
因此沒有符合條件的子字符串，返回空字符串。
提示：
1 <= s.length, t.length <= 105
s 和 t 由英文字母組成
進(jìn)階：你能設(shè)計一個在 o(n) 時間內(nèi)解決此問題的算法嗎？
解法1：滑動窗口
思路：
(滑動窗口) O(n)
這道題要求我們返回字符串 s中包含字符串 t 的全部字符的最小窗口，我們利用滑動窗口的思想解決這個問題。因此我們需要兩個哈希表，hs哈希表維護(hù)的是s字符串中滑動窗口中各個字符出現(xiàn)多少次，ht哈希表維護(hù)的是t字符串各個字符出現(xiàn)多少次。如果hs哈希表中包含ht哈希表中的所有字符，并且對應(yīng)的個數(shù)都不小于ht哈希表中各個字符的個數(shù)，那么說明當(dāng)前的窗口是可行的，可行中的長度最短的滑動窗口就是答案。
過程如下：
1、遍歷t字符串，用ht哈希表記錄t字符串各個字符出現(xiàn)的次數(shù)。
2、定義兩個指針j和i，j指針用于收縮窗口，i指針用于延伸窗口，則區(qū)間[j,i]表示當(dāng)前滑動窗口。首先讓i和j指針都指向字符串s開頭，然后枚舉整個字符串s ，枚舉過程中，不斷增加i使滑動窗口增大，相當(dāng)于向右擴(kuò)展滑動窗口。
3、每次向右擴(kuò)展滑動窗口一步，將s[i]加入滑動窗口中，而新加入了s[i]，相當(dāng)于滑動窗口維護(hù)的字符數(shù)加一，即hs[s[i]]++。
4、對于新加入的字符s[i],如果hs[s[i]] <= ht[s[i]]，說明當(dāng)前新加入的字符s[i]是必需的，且還未到達(dá)字符串t所要求的數(shù)量。我們還需要事先定義一個cnt變量， cnt維護(hù)的是s字符串[j,i]區(qū)間中滿足t字符串的元素的個數(shù)，記錄相對應(yīng)字符的總數(shù)。新加入的字符s[i]必需，則cnt++。
5、我們向右擴(kuò)展滑動窗口的同時也不能忘記收縮滑動窗口。因此當(dāng)hs[s[j]] > ht[s[j]時，說明hs哈希表中s[j]的數(shù)量多于ht哈希表中s[j]的數(shù)量，此時我們就需要向右收縮滑動窗口，j++并使hs[s[j]]–，即hs[s[j ++ ]] --。
6、當(dāng)cnt == t.size時，說明此時滑動窗口包含符串 t 的全部字符。我們重復(fù)上述過程找到最小窗口即為答案。
時間復(fù)雜度分析： 兩個指針都嚴(yán)格遞增，最多移動 n 次，所以總時間復(fù)雜度是 O(n)。
代碼：
class Solution { public:string minWindow(string s, string t) {unordered_map<char,int> sMap,tMap;for(auto& c:t) tMap[c]++;string result;int cnt = 0;int left = 0, right = 0;while(right < s.size()){//[left,right)sMap[s[right]]++;if(sMap[s[right]] <= tMap[s[right]]) cnt++;//必須加入的元素right++;while(sMap[s[left]] > tMap[s[left]]){sMap[s[left]]--;left++;}if(cnt == t.size()){if(result.empty() || right-left<result.size()){//result為空或遇到了更短的長度result = s.substr(left,right-left);}}}return result;} };3. 無重復(fù)字符的最長子串
力扣鏈接
給定一個字符串 s ，請你找出其中不含有重復(fù)字符的 最長子串 的長度。
示例 1:
輸入: s = “abcabcbb”
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 “abc”，所以其長度為 3。
示例 2:
輸入: s = “bbbbb”
輸出: 1
解釋: 因為無重復(fù)字符的最長子串是 “b”，所以其長度為 1。
示例 3:
輸入: s = “pwwkew”
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 “wke”，所以其長度為 3。
請注意，你的答案必須是 子串 的長度，“pwke” 是一個子序列，不是子串。
示例 4:
輸入: s = “”
輸出: 0
提示：
0 <= s.length <= 5 * 104
s 由英文字母、數(shù)字、符號和空格組成
解法1：滑動窗口+哈希
思路：
這道題主要用到思路是：滑動窗口
什么是滑動窗口？
其實就是一個隊列,比如例題中的 abcabcbb，進(jìn)入這個隊列（窗口）為 abc 滿足題目要求，當(dāng)再進(jìn)入 a，隊列變成了 abca，這時候不滿足要求。所以，我們要移動這個隊列！
如何移動？
我們只要把隊列的左邊的元素移出就行了，直到滿足題目要求！
一直維持這樣的隊列，找出隊列出現(xiàn)最長的長度時候，求出解！
時間復(fù)雜度：O(n)
代碼1：
class Solution { public:int lengthOfLongestSubstring(string s) {unordered_map<char,int> umap;int left = 0, right = 0, result = 0;while(right < s.size()){if(umap[s[right]] == 0){//不是重復(fù)字符，右指針右移umap[s[right]]++;right++;}else{//是重復(fù)字符，左指針右移umap[s[left]]--;left++;}result = max(result,right-left);}return result;} };代碼2：
class Solution { public:int lengthOfLongestSubstring(string s) {if (s.size() == 0) return 0;unordered_set<char> uset;int left = 0;int count = 0;for(int right = 0;right<s.size();right++){while(uset.find(s[right])!=uset.end()) {uset.erase(s[left]);left++;} count = max(count,right-left+1); uset.insert(s[right]);}return count;} };424. 替換后的最長重復(fù)字符
力扣鏈接
給你一個僅由大寫英文字母組成的字符串，你可以將任意位置上的字符替換成另外的字符，總共可最多替換 k 次。在執(zhí)行上述操作后，找到包含重復(fù)字母的最長子串的長度。
注意：字符串長度 和 k 不會超過 104。
示例 1：
輸入：s = “ABAB”, k = 2
輸出：4
解釋：用兩個’A’替換為兩個’B’,反之亦然。
示例 2：
輸入：s = “AABABBA”, k = 1
輸出：4
解釋：
將中間的一個’A’替換為’B’,字符串變?yōu)?“AABBBBA”。
子串 “BBBB” 有最長重復(fù)字母, 答案為 4。
解法1：滑動窗口
思路：
我們可以枚舉字符串中的每一個位置作為右端點，然后找到其最遠(yuǎn)的左端點的位置，滿足該區(qū)間內(nèi)除了出現(xiàn)次數(shù)最多的那一類字符之外，剩余的字符（即非最長重復(fù)字符）數(shù)量不超過 k個。
代碼：
class Solution { public:int characterReplacement(string s, int k) {unordered_map<char,int> umap;int left = 0, right = 0, result = 0, maxCnt = 0;while(right < s.size()){umap[s[right]]++;maxCnt = max(maxCnt,umap[s[right]]);right++;while(right - left > maxCnt + k){umap[s[left]]--;left++;}result = max(result,right - left);}return result;} };相似題目：485. 最大連續(xù) 1 的個數(shù)
力扣鏈接
給定一個二進(jìn)制數(shù)組， 計算其中最大連續(xù) 1 的個數(shù)。
示例：
輸入：[1,1,0,1,1,1]
輸出：3
解釋：開頭的兩位和最后的三位都是連續(xù) 1 ，所以最大連續(xù) 1 的個數(shù)是 3.
提示：
輸入的數(shù)組只包含 0 和 1 。
輸入數(shù)組的長度是正整數(shù)，且不超過 10,000。
解法1：數(shù)組+一次遍歷
思路：
為了得到數(shù)組中最大連續(xù) 1 的個數(shù)，需要遍歷數(shù)組，并記錄最大的連續(xù) 11的個數(shù)和當(dāng)前的連續(xù) 1 的個數(shù)。如果當(dāng)前元素是 1，則將當(dāng)前的連續(xù) 1 的個數(shù)加 1，否則，使用之前的連續(xù) 1 的個數(shù)更新最大的連續(xù) 1 的個數(shù)，并將當(dāng)前的連續(xù) 1 的個數(shù)清零。
遍歷數(shù)組結(jié)束之后，需要再次使用當(dāng)前的連續(xù) 1的個數(shù)更新最大的連續(xù) 1 的個數(shù)，因為數(shù)組的最后一個元素可能是 1，且最長連續(xù) 1 的子數(shù)組可能出現(xiàn)在數(shù)組的末尾，如果遍歷數(shù)組結(jié)束之后不更新最大的連續(xù) 1 的個數(shù)，則會導(dǎo)致結(jié)果錯誤。
代碼：
class Solution { public:int findMaxConsecutiveOnes(vector<int>& nums) {int count = 0, result = 0;for(int i = 0;i<nums.size();i++){if(nums[i] == 1) count++;else{result = max(result,count);count = 0;}}result = max(result,count);return result;} };劍指 Offer 59 - I. 滑動窗口的最大值
力扣鏈接
給定一個數(shù)組 nums 和滑動窗口的大小 k，請找出所有滑動窗口里的最大值。
示例:
輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7]
解釋:
滑動窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
提示：
你可以假設(shè) k 總是有效的，在輸入數(shù)組不為空的情況下，1 ≤ k ≤ 輸入數(shù)組的大小。
注意：本題與主站 239 題相同：https://leetcode-cn.com/problems/sliding-window-maximum/
解法1：滑動窗口+單調(diào)隊列+雙向隊列
思路：
這是使用單調(diào)隊列的經(jīng)典題目。
（1）我們需要一個隊列，這個隊列呢，放進(jìn)去窗口里的元素，然后隨著窗口的移動，隊列也一進(jìn)一出，每次移動之后，隊列告訴我們里面的最大值是什么。
這個隊列應(yīng)該長這個樣子：
class MyQueue { public:void pop(int value) {}void push(int value) {}int front() {return que.front();} };每次窗口移動的時候，調(diào)用que.pop(滑動窗口中移除元素的數(shù)值)，que.push(滑動窗口添加元素的數(shù)值)，然后que.front()就返回我們要的最大值。
這么個隊列香不香，要是有現(xiàn)成的這種數(shù)據(jù)結(jié)構(gòu)是不是更香了！可惜了，沒有！ 我們需要自己實現(xiàn)這么個隊列。
然后在分析一下，隊列里的元素一定是要排序的，而且要**最大值放在出隊口，**要不然怎么知道最大值呢。
但如果把窗口里的元素都放進(jìn)隊列里，窗口移動的時候，隊列需要彈出元素。那么問題來了，已經(jīng)排序之后的隊列 怎么能把窗口要移除的元素（這個元素可不一定是最大值）彈出呢。
其實隊列沒有必要維護(hù)窗口里的所有元素，只需要維護(hù)有可能成為窗口里最大值的元素就可以了，同時保證隊里里的元素數(shù)值是由大到小的。
那么這個維護(hù)元素單調(diào)遞減的隊列就叫做單調(diào)隊列，即單調(diào)遞減或單調(diào)遞增的隊列。C++中沒有直接支持單調(diào)隊列，需要我們自己來一個單調(diào)隊列
不要以為實現(xiàn)的單調(diào)隊列就是 對窗口里面的數(shù)進(jìn)行排序，如果排序的話，那和優(yōu)先級隊列又有什么區(qū)別了呢。
（2）對于窗口里的元素{2, 3, 5, 1 ,4}，單調(diào)隊列里只維護(hù){5, 4} 就夠了，保持單調(diào)隊列里單調(diào)遞減，此時隊列出口元素就是窗口里最大元素。
此時大家應(yīng)該懷疑單調(diào)隊列里維護(hù)著{5, 4} 怎么配合窗口經(jīng)行滑動呢？
設(shè)計單調(diào)隊列的時候，pop，和push操作要保持如下規(guī)則：
1.pop(value)：如果窗口移除的元素value等于單調(diào)隊列的出口元素，那么隊列彈出元素，否則不用任何操作
2.push(value)：如果push的元素value大于入口元素的數(shù)值，那么就將隊列入口的元素彈出，直到push元素的數(shù)值小于等于隊列入口元素的數(shù)值為止
保持如上規(guī)則，每次窗口移動的時候，只要問que.front()就可以返回當(dāng)前窗口的最大值。
那么我們用什么數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)這個單調(diào)隊列呢？使用deque最為合適，常用的queue在沒有指定容器的情況下，deque就是默認(rèn)底層容器。
class MyQueue { //單調(diào)隊列（從大到小） public:deque<int> que; // 使用deque來實現(xiàn)單調(diào)隊列// 每次彈出的時候，比較當(dāng)前要彈出的數(shù)值是否等于隊列出口元素的數(shù)值，如果相等則彈出。// 同時pop之前判斷隊列當(dāng)前是否為空。void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}// 如果push的數(shù)值大于入口元素的數(shù)值，那么就將隊列后端的數(shù)值彈出，直到push的數(shù)值小于等于隊列入口元素的數(shù)值為止。// 這樣就保持了隊列里的數(shù)值是單調(diào)從大到小的了。void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}// 查詢當(dāng)前隊列里的最大值 直接返回隊列前端也就是front就可以了。int front() {return que.front();} };代碼：
class Solution { public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {//單調(diào)隊列deque<int> dq;for(int i = 0;i<k;i++){while(!dq.empty() && nums[i] >= nums[dq.back()]){dq.pop_back();}dq.push_back(i);}vector<int> res = {nums[dq.front()]};for(int i = k;i<nums.size();i++){while(!dq.empty() && nums[i] >= nums[dq.back()]){dq.pop_back();}dq.push_back(i);while(dq.front() <= i-k) dq.pop_front();res.push_back(nums[dq.front()]);}return res;} };復(fù)雜度分析：
時間復(fù)雜度，使用單調(diào)隊列的時間復(fù)雜度是 O(n)O(n)O(n)。
有的同學(xué)可能想了，在隊列中 push元素的過程中，還有pop操作呢，感覺不是純粹的O(n)O(n)O(n)。
其實，大家可以自己觀察一下單調(diào)隊列的實現(xiàn)，nums 中的每個元素最多也就被 push_back 和 pop_back 各一次，沒有任何多余操作，所以整體的復(fù)雜度還是 O(n)O(n)O(n)。
空間復(fù)雜度因為我們定義一個輔助隊列，所以是O(k)O(k)O(k)
解法2：優(yōu)先隊列+滑動窗口
思路：
代碼：
class Solution { public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {if(nums.size() == 0) return {};//大根堆priority_queue<pair<int,int>> pq;//num[i]--位置for(int i = 0;i<k;i++){pq.push({nums[i],i});}vector<int> result;result.push_back(pq.top().first);for(int i = k;i<nums.size();i++){pq.push({nums[i],i});while(pq.top().second <= i-k){pq.pop();}result.push_back(pq.top().first);}return result;} };相似題目：劍指 Offer 59 - II. 隊列的最大值
力扣鏈接
請定義一個隊列并實現(xiàn)函數(shù) max_value 得到隊列里的最大值，要求函數(shù)max_value、push_back 和 pop_front 的均攤時間復(fù)雜度都是O(1)。
若隊列為空，pop_front 和 max_value 需要返回 -1
示例 1：
輸入:
[“MaxQueue”,“push_back”,“push_back”,“max_value”,“pop_front”,“max_value”]
[[],[1],[2],[],[],[]]
輸出: [null,null,null,2,1,2]
示例 2：
輸入:
[“MaxQueue”,“pop_front”,“max_value”]
[[],[],[]]
輸出: [null,-1,-1]
限制：
1 <= push_back,pop_front,max_value的總操作數(shù) <= 10000
1 <= value <= 10^5
解法1：單調(diào)隊列+滑動窗口
思路：
代碼：
1052. 愛生氣的書店老板
力扣鏈接
有一個書店老板，他的書店開了 n 分鐘。每分鐘都有一些顧客進(jìn)入這家商店。給定一個長度為 n 的整數(shù)數(shù)組 customers ，其中 customers[i] 是在第 i 分鐘開始時進(jìn)入商店的顧客的編號，所有這些顧客在第 i 分鐘結(jié)束后離開。
在某些時候，書店老板會生氣。 如果書店老板在第 i 分鐘生氣，那么 grumpy[i] = 1，否則 grumpy[i] = 0。
當(dāng)書店老板生氣時，那一分鐘的顧客就會不滿意，若老板不生氣則顧客是滿意的。
書店老板知道一個秘密技巧，能抑制自己的情緒，可以讓自己連續(xù) minutes 分鐘不生氣，但卻只能使用一次。
請你返回 這一天營業(yè)下來，最多有多少客戶能夠感到滿意 。
示例 1：
輸入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
輸出：16
解釋：書店老板在最后 3 分鐘保持冷靜。
感到滿意的最大客戶數(shù)量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
示例 2：
輸入：customers = [1], grumpy = [0], minutes = 1
輸出：1
提示：
n == customers.length == grumpy.length
1 <= minutes <= n <= 2 * 104
0 <= customers[i] <= 1000
grumpy[i] == 0 or 1
解法1：數(shù)組+滑動窗口
思路：
代碼：
class Solution { public:int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {int n = customers.size();int sum = 0, maxN = 0;//不生氣時的總數(shù) 生氣區(qū)間內(nèi)使用技巧的最大值for(int i = 0;i<n;i++){if(grumpy[i] == 0){sum += customers[i];customers[i] = 0;}}int num = 0;for(int i = 0, j = 0;i<n;i++){num += customers[i];if(i-j+1>minutes){num -= customers[j];j++;}maxN = max(maxN,num);}return sum + maxN;} };209. 長度最小的子數(shù)組
力扣鏈接
給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) target 。
找出該數(shù)組中滿足其和 ≥ target 的長度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其長度。如果不存在符合條件的子數(shù)組，返回 0 。
示例 1：
輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組。
示例 2：
輸入：target = 4, nums = [1,4,4]
輸出：1
示例 3：
輸入：target = 11, nums = [1,1,1,1,1,1,1,1]
輸出：0
提示：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
進(jìn)階：
如果你已經(jīng)實現(xiàn) O(n) 時間復(fù)雜度的解法, 請嘗試設(shè)計一個 O(n log(n)) 時間復(fù)雜度的解法。
解法1：滑動窗口
class Solution { public:int minSubArrayLen(int target, vector<int>& nums) {//滑動窗口int result = INT_MAX;int sum = 0;for(int i = 0, j = 0;j<nums.size();j++){sum += nums[j];while(sum >= target){result = min(j-i+1,result);sum -= nums[i];i++;}}return result == INT_MAX ? 0:result;} };相似題目：718. 最長重復(fù)子數(shù)組
力扣鏈接
給兩個整數(shù)數(shù)組 nums1 和 nums2 ，返回 兩個數(shù)組中 公共的 、長度最長的子數(shù)組的長度 。
示例 1：
輸入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
輸出：3
解釋：長度最長的公共子數(shù)組是 [3,2,1] 。
示例 2：
輸入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
輸出：5
提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100
解法1：動態(tài)規(guī)劃
確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[i][j] ：以下標(biāo)i - 1為結(jié)尾的A，和以下標(biāo)j - 1為結(jié)尾的B，最長重復(fù)子數(shù)組長度為dp[i][j]。 （特別注意： “以下標(biāo)i - 1為結(jié)尾的A” 標(biāo)明一定是 以A[i-1]為結(jié)尾的字符串 ）
567. 字符串的排列
力扣鏈接
給你兩個字符串 s1 和 s2 ，寫一個函數(shù)來判斷 s2 是否包含 s1 的排列。如果是，返回 true ；否則，返回 false 。
換句話說，s1 的排列之一是 s2 的 子串 。
示例 1：
輸入：s1 = “ab” s2 = “eidbaooo”
輸出：true
解釋：s2 包含 s1 的排列之一 (“ba”).
示例 2：
輸入：s1= “ab” s2 = “eidboaoo”
輸出：false
提示：
1 <= s1.length, s2.length <= 104
s1 和 s2 僅包含小寫字母
解法1:滑動窗口
class Solution { public:bool checkInclusion(string s1, string s2) {//滑動窗口unordered_map<char,int> s1Map, s2Map;for(char c:s1) s1Map[c]++;int slow = 0, fast = 0;for(;fast<s2.size();fast++){s2Map[s2[fast]]++;while(s2Map[s2[fast]] > s1Map[s2[fast]]){s2Map[s2[slow]]--;slow++;}if(fast - slow + 1 == s1.size()) return true;}return false;} };總結(jié)
以上是生活随笔為你收集整理的[力扣刷题总结](双指针篇)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 基本的ubunutu命令以及代码环境配置
- 下一篇： linux中gawk用法,Linux -