LeetCode：雙指針法

雙指針法通常是指使用兩個(gè)指針相向而行或同向而行來遍歷對(duì)象（如數(shù)組、鏈表或字符串），以避免多層循環(huán)，從而降低算法的時(shí)間復(fù)雜度。

正序同向而行（快慢指針）

移除元素

移除元素

class Solution {
public:int removeElement(vector<int>& nums,  int val) {int slow = 0, fast = 0; while (fast < nums.size()) {  if (nums[fast] != val) {       // fast_i沒遇到目標(biāo)值nums[slow] = nums[fast];   // 保留 nums[fast]// slow和fast都前進(jìn)一步slow++;    fast++; }else{                         // 遇到目標(biāo)值，slow不動(dòng)，fast前進(jìn)一步fast++; }}return slow;    }
};

簡化代碼：

class Solution {
public:int removeElement(vector<int>& nums,  int val) {int slow = 0, fast = 0; while (fast < nums.size()) {  if (nums[fast] != val) {    nums[slow++] = nums[fast];   }fast++; }return slow;    
}
};

移動(dòng)零（Hot 100）

移動(dòng)零

class Solution {
public:void moveZeroes(vector<int>& nums) {int  slow = 0, fast = 0;while (fast < nums.size()) {if (nums[fast] != 0) { // fast 指向非零數(shù)，swap(nums[slow], nums[fast]); // 保留非零數(shù)slow++;  // slow和fast 都前進(jìn)一步  }fast++; // 指向零數(shù) slow不動(dòng)，fast前進(jìn)一步}}
};

刪除有序數(shù)組中的重復(fù)項(xiàng)

刪除有序數(shù)組中的重復(fù)項(xiàng)

class Solution {
public:int removeDuplicates(vector<int>& nums) {int fast = 1, slow = 1;while (fast <  nums.size()) {// fast 沒指向重復(fù)項(xiàng)，slow和fast都移動(dòng)if (nums[fast] != nums[fast - 1]) {nums[slow] = nums[fast]; // 保留非重復(fù)項(xiàng)slow++;   // slow指向未保留的元素，可能是要去除的元素}fast++;  // fast指向重復(fù)項(xiàng)，則不讓slow移動(dòng)}return slow;}
};

顏色分類（Hot 100）

顏色分類

class Solution {
public:void sortColors(vector<int>& nums) {int slow = 0, fast = 0;// 把0往前移while(fast < nums.size()) {if (nums[fast] == 0) {swap(nums[fast], nums[slow]);++slow;}++fast;}fast = slow;// 把1往前移while(fast < nums.size()) {if (nums[fast] == 1) {swap(nums[fast], nums[slow]);++slow;}++fast;}}
};

壓縮字符串

壓縮字符串

class Solution {
public:int compress(vector<char>& chars) {int slow = 0;int fast = 0;while(fast < chars.size()){char cur = chars[fast];int count = 0;         // 重復(fù)數(shù)量while(fast < chars.size() && chars[fast] == cur){fast++;count++;}chars[slow++] = cur;   // 記錄當(dāng)前字符if(count > 1){         // 記錄當(dāng)前字符重復(fù)數(shù)量for(char c: to_string(count)) chars[slow++] = c;}}return slow;}   
};

移除鏈表元素

移除鏈表元素

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummy_head = new ListNode(0, head);ListNode* cur = dummy_head;// 雙指針：cur和 cur.nextwhile(cur->next != nullptr){if(cur->next->val != val){cur = cur->next;}else{cur->next = cur->next->next;}}return dummy_head->next;}
};

刪除排序鏈表中的重復(fù)元素

刪除排序鏈表中的重復(fù)元素

class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if (head == nullptr) return head;// 第一個(gè)節(jié)點(diǎn)肯定不是重復(fù)元素ListNode* cur = head;// 雙指針：cur和 cur.nextwhile(cur->next != nullptr){if(cur->next->val != cur->val){cur = cur->next;}else{cur->next = cur->next->next;}}return head;}
};

刪除排序鏈表中的重復(fù)元素 II

刪除排序鏈表中的重復(fù)元素 II

class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {ListNode* hair = new ListNode(0,head);ListNode* cur = hair;while(cur->next && cur->next->next){if(cur->next->next->val == cur->next->val) // 數(shù)值val存在重復(fù){int val = cur->next->val;   // 記錄數(shù)值// 去掉cur->next之后所有值為val的節(jié)點(diǎn)while(cur->next && cur->next->val == val){ cur->next = cur->next->next;}}else{cur = cur->next;}   }return hair->next;}
};

反轉(zhuǎn)鏈表 （Hot 100）

反轉(zhuǎn)鏈表

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* prev = nullptr;ListNode* cur = head;while(cur){ListNode* temp = cur->next;cur->next = prev;prev = cur;cur =temp;}return prev;}
};

刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn) （Hot 100）

刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(0, head);// 相鄰節(jié)點(diǎn)fast slowListNode* fast = head;ListNode* slow = dummy;// 使得slow和fast之間的節(jié)點(diǎn)數(shù)為nfor (int i = 0; i < n; ++i) fast = fast->next;  // 同時(shí)移動(dòng)slow和fast，直到fast為nullptrwhile (fast) {fast = fast->next;slow = slow->next;}// 刪除倒數(shù)第n個(gè)節(jié)點(diǎn)slow->next = slow->next->next;return dummy->next;}
};

鏈表的中間結(jié)點(diǎn)

鏈表的中間結(jié)點(diǎn)

class Solution {
public:ListNode* middleNode(ListNode* head) {ListNode* slow = head;ListNode* fast = head;while (fast != nullptr && fast->next != nullptr) {// fast 速度是slow的兩倍，fast達(dá)到尾部時(shí)，slow到達(dá)中間slow = slow->next;fast = fast->next->next;}return slow;}
};

K 個(gè)一組翻轉(zhuǎn)鏈表 （Hot 100）

K 個(gè)一組翻轉(zhuǎn)鏈表

class Solution {
private:void reverseGroup(ListNode*& head, ListNode*& tail,int k){ListNode* pre = nullptr;ListNode* cur = head;for(int i = 0 ; i< k; i++){ListNode* temp = cur->next;cur->next = pre;pre = cur;cur = temp;}}public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* dummy = new ListNode(0,head);ListNode* tail = dummy;while(head){ListNode* pre = tail; for(int i = 0 ;i < k; i++){tail = tail->next;// 如果節(jié)點(diǎn)總數(shù)不是 k 的整數(shù)倍，那么最后剩余的節(jié)點(diǎn)保持原有順序。if(!tail) return dummy->next;}ListNode* temp = tail->next;reverseGroup(head, tail, k);swap(head, tail);  // 子鏈表頭變成尾，尾變成頭// 把子鏈表重新接回原鏈表pre->next = head;tail->next = temp;head = temp;}return dummy->next;}
};

排序鏈表 （Hot 100）

排序鏈表

class Solution {
public:ListNode* sortList(ListNode* head) {if (head == nullptr)  return head;return sort(head, nullptr);}// 歸并排序ListNode* sort(ListNode* head, ListNode* tail) {// 如果鏈表只有一個(gè)節(jié)點(diǎn)，將其與后續(xù)節(jié)點(diǎn)斷開并返回該節(jié)點(diǎn)if (head->next == tail) {head->next = nullptr;return head;}ListNode* slow = head, *fast = head;while (fast != tail && fast->next != tail) {slow = slow->next;fast = fast->next->next;}ListNode* mid = slow;return merge(sort(head, mid), sort(mid, tail));}// 升序合并ListNode* merge(ListNode* head1, ListNode* head2) {ListNode* dummyHead = new ListNode(0);ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;while (temp1 != nullptr && temp2 != nullptr) {if (temp1->val <= temp2->val) {temp->next = temp1;temp1 = temp1->next;} else {temp->next = temp2;temp2 = temp2->next;}temp = temp->next;}if (temp1 != nullptr)  temp->next = temp1;     else if (temp2 != nullptr) temp->next = temp2;return dummyHead->next;}
};

倒序同向而行

合并兩個(gè)有序數(shù)組（Hot 100）

合并兩個(gè)有序數(shù)組

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int i = nums1.size() - 1;m--;n--;while(n >= 0){if(m >= 0 && nums1[m] > nums2[n]) nums1[i--] = nums1[m--];else nums1[i--] = nums2[n--]; }}
};

尋找兩個(gè)正序數(shù)組的中位數(shù)（Hot 100）

尋找兩個(gè)正序數(shù)組的中位數(shù)

class Solution {
public:double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {  std::vector<int> merged;  int i = 0, j = 0;  int m = nums1.size(), n = nums2.size();  // 合并兩個(gè)數(shù)組  while (i < m && j < n) {  if (nums1[i] < nums2[j]) {  merged.push_back(nums1[i++]);  } else {  merged.push_back(nums2[j++]);  }  }  // 添加剩余的元素  while (i < m) merged.push_back(nums1[i++]); while (j < n)  merged.push_back(nums2[j++]);  int totalSize = merged.size();  if (totalSize % 2 == 1) {  // 奇數(shù)個(gè)元素，中位數(shù)是中間的那個(gè)  return merged[totalSize / 2];  } else {  // 偶數(shù)個(gè)元素，中位數(shù)是中間兩個(gè)數(shù)的平均值  return (merged[totalSize / 2 - 1] + merged[totalSize / 2]) / 2.0;  }  }  
};

字符串相加

字符串相加

class Solution {
public:string addStrings(string num1, string num2) {int i = num1.size() - 1;int j = num2.size() - 1;int add = 0;string result = "";while(i >= 0 || j >= 0 || add > 0){int x = i >= 0 ? num1[i] - '0' : 0;int y = j >= 0 ? num2[j] - '0' : 0;int val = x + y + add;result.push_back('0' + val % 10);add = val / 10;i --; j--;}reverse(result.begin(), result.end());return result;}
};

反轉(zhuǎn)字符串中的單詞

反轉(zhuǎn)字符串中的單詞

// https://leetcode.cn/problems/reverse-words-in-a-string/solutions/2361551/151-fan-zhuan-zi-fu-chuan-zhong-de-dan-c-yb1r/class Solution {
public:std::string reverseWords(std::string s) {std::vector<std::string> wordsVector; // 存儲(chǔ)分割后的單詞的向量int i, j;i = s.size() - 1; // i 從字符串末尾開始向前掃描j = i; // j 用于標(biāo)記單詞的尾字符索引while (i >= 0) {// 跳過單詞間的空格while (i >= 0 && s[i] == ' ')  i--;j = i; // 更新單詞的尾字符索引while (i >= 0 && s[i] != ' ') i--; // 找到單詞前的空格// 將找到的單詞添加到向量中（注意要避免將空格作為單詞存儲(chǔ)）if (i != j)  wordsVector.push_back(s.substr(i + 1, (j - i)));}std::string result;// 將向量中的單詞連接成一個(gè)字符串for (int n = 0; n < wordsVector.size(); ++n) {result += wordsVector[n];if (n != wordsVector.size() - 1) result += ' '; // 添加單詞間的空格}return result;}
};

相向而行

有序數(shù)組的平方

有序數(shù)組的平方

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {vector<int> result(nums.size());int l = 0;int r = nums.size() - 1;int pos = nums.size() - 1;// 非遞減數(shù)組平方后，數(shù)值由兩側(cè)向中間遞減while(l <= r){// 左側(cè)的值比右側(cè)的值高if(nums[l] * nums[l] > nums[r] * nums[r]){result[pos] = nums[l] * nums[l];l++; }else{ // 右側(cè)的值比左側(cè)的值高result[pos] = nums[r] * nums[r];r--;}pos--;}return result;}
};

盛最多水的容器 (Hot100)

盛最多水的容器

class Solution {
public:int maxArea(vector<int>& height) {int l = 0;int r = height.size() - 1;int result = 0;while(l < r){int capacity = min(height[l],height[r])*(r -l);result = max(result, capacity);// 寬度縮小，嘗試增大最小高度if(height[l] <= height[r]) l++;  else r--;}return result;}
};

接雨水 (Hot 100)

接雨水

class Solution {
public:int trap(vector<int>& height) {int l = 0;int r = height.size() - 1;int ans = 0;int left_max = INT_MIN;int right_max = INT_MIN;while(l < r){left_max = max(left_max, height[l]);right_max = max(right_max, height[r]);if(height[l] < height[r] ){   // 滿足： height[l] < height[r] 且 height[l] <= left_maxans += left_max - height[l];l++;}else{ans += right_max - height[r];r--;}}return ans;}
};

三數(shù)之和 (Hot 100)

三數(shù)之和

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {  vector<vector<int>> result;  // 對(duì)數(shù)組進(jìn)行排序，從左到右遞增sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); i++) {  // 跳過第一個(gè)數(shù)的重復(fù)元素以避免重復(fù)的三元組  // 保證i在相同值的最左，這樣left才可以取相同值if (i > 0 && nums[i] == nums[i - 1]) continue;  // a≤b≤c，保證了只有 (a,b,c)這個(gè)順序會(huì)被枚舉到int left = i + 1; int right = nums.size() - 1;  while (left < right) {  int sum = nums[i] + nums[left] + nums[right];  if (sum < 0) left++;       // 如果和小于0，右移左指針，嘗試增大值 else if (sum > 0) right--; // 如果和大于0，左移右指針，嘗試較小值else {   //  跳過第二個(gè)數(shù)的重復(fù)元素, 保證left為最右while (left < right && nums[left] == nums[left + 1]) left++;  //  跳過第三個(gè)數(shù)的重復(fù)元素, 保證left為最左while (left < right && nums[right] == nums[right - 1]) right--;  // 找到了一個(gè)和為0的組合  result.push_back({nums[i], nums[left], nums[right]}); // 繼續(xù)尋找下一個(gè)組合left++;  right--;  }             }  }  return result;  } 
};

反轉(zhuǎn)字符串

反轉(zhuǎn)字符串

class Solution {
public:void reverseString(vector<char>& s) {int n = s.size();int left = 0, right = n - 1;while (left < right) {swap(s[left++], s[right--]);}}
};

滑動(dòng)窗口

滑動(dòng)窗口通過雙指針實(shí)現(xiàn)，一個(gè)指針（右指針）用于擴(kuò)展窗口，另一個(gè)指針（左指針）收縮窗口。與普通的雙指針不同的是，滑動(dòng)窗口法的計(jì)算過程一般涉及雙指針之間的值，而不僅僅是兩個(gè)指針指向的值。

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

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

class Solution {
public:int lengthOfLongestSubstring(string s) {if (s.size() == 0)  return 0;unordered_set<char> char_set; // 窗口內(nèi)的字符int ans = 0;int left = 0;for (int right = 0; right < s.size(); right++) {while (char_set.count(s[right]) != 0)  { // 重復(fù)了char_set.erase(s[left]);left++;   // left指向s[right]最后一次出現(xiàn)的地方的下一個(gè)位置}ans = max(ans, right - left + 1);char_set.insert(s[right]);}return ans;}
};

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

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

class Solution {
public:vector<int> findAnagrams(string s, string p) {int s_len = s.size(), p_len = p.size();if (s_len < p_len) return vector<int>();vector<int> ans;// 存放字符串中字母(a-z)出現(xiàn)的詞頻vector<int> s_count(26);vector<int> p_count(26);// 當(dāng)滑動(dòng)窗口的首位在s[0]處時(shí)（相當(dāng)于放置滑動(dòng)窗口進(jìn)入數(shù)組）for (int i = 0; i < p_len; ++i) {++s_count[s[i] - 'a'];  //記錄s中前p_len個(gè)字母的詞頻++p_count[p[i] - 'a'];  //記錄要尋找的字符串中每個(gè)字母的詞頻(只用進(jìn)行一次來確定)}// 判斷放置處是否有異位詞if (s_count == p_count) ans.push_back(0);//開始讓窗口向右進(jìn)行滑動(dòng),遍歷起始索引for (int i = 1; i <= s_len - p_len; ++i) { // 向右移動(dòng)滑塊：相當(dāng)于去掉左邊第一個(gè)字符，在右邊加入一個(gè)字母--s_count[s[i - 1] - 'a'];            // 左邊去掉的字母的詞頻減1++s_count[s[i + p_len - 1] - 'a'];    // 右邊加入的字母的詞頻加1if (s_count == p_count) {      // 判斷滑動(dòng)后處，是否有異位詞ans.push_back(i);}}return ans;}
};

最小覆蓋子串（Hot100)

最小覆蓋子串

class Solution {
public:// 檢查當(dāng)前窗口是否覆蓋目標(biāo)字符串bool check(unordered_map<char, int>& map_t,unordered_map<char, int>& map_s) {for (const auto& p : map_t) {if (map_s[p.first] < p.second)return false;}return true;}string minWindow(string s, string t) {// 最小覆蓋子串的起始位置和長度int ans_left = -1, ans_len = INT_MAX;// map_t：記錄目標(biāo)字符串t中每個(gè)字符及其出現(xiàn)次數(shù)，// map_s：記錄記錄s在當(dāng)前窗口內(nèi)每個(gè)字符的出現(xiàn)次數(shù)unordered_map<char, int> map_t, map_s;// 初始化ori：記錄目標(biāo)字符串t每個(gè)字符及其出現(xiàn)次數(shù)for (const auto& c : t)++map_t[c];// 窗口左右指針int left = 0, right = 0;// 向右擴(kuò)大窗口直到右指針達(dá)到s末尾while (right < int(s.size())) {// 將字符s[right]加入到map_s中if (map_t.find(s[right]) != map_t.end())++map_s[s[right]];// 當(dāng)前窗口包含了目標(biāo)字符串t中的所有字符時(shí)while (check(map_t, map_s) && left <= right) {if (right - left + 1 <ans_len) { // 更新最小覆蓋子串的起始位置和長度ans_len = right - left + 1;ans_left = left;}// 將左指針指向的字符從cnt中移除if (map_t.find(s[left]) != map_t.end())--map_s[s[left]];// 移動(dòng)左指針，縮小窗口++left;}++right; //  向右擴(kuò)大窗口}// 如果ans_left仍為-1，說明s中不存在包含t的子串，返回空字符串// 否則，返回從ans_left開始，長度為len的子串return ans_left == -1 ? string() : s.substr(ans_left, ans_len);}
};

滑動(dòng)窗口最大值（Hot100)

滑動(dòng)窗口最大值

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {if(nums.size() == 0 || k == 0) return {};deque<int> deque;  vector<int> result(nums.size() - k + 1);int  left = 1 - k,right = 0;while(right < nums.size()) {// 隊(duì)列最前元素為nums[left-1]，則刪除if(left > 0 && deque.front() == nums[left - 1]) deque.pop_front();// 單調(diào)隊(duì)列  刪除小于nums[right]的數(shù)，保持 deque 遞減while(!deque.empty() && deque.back() < nums[right]) deque.pop_back(); // 添加nums[right]deque.push_back(nums[right]);// 記錄窗口最大值if(left >= 0) result[left] = deque.front();left++, right++;}return result;}
};