專題一：雙指針

---

1. 移動零

---

題目解析

算法原理

代碼編寫

// 寫法一
class Solution 
{
public:void moveZeroes(vector<int>& nums) {// 1、下標初始化int dest = -1, cur = 0;// 2、數組劃分while(cur < nums.size()){if(nums[cur]) swap(nums[++dest], nums[cur++]);else ++cur;}}
};// 寫法二
class Solution 
{
public:void moveZeroes(vector<int>& nums) {for(int dest = -1, cur = 0; cur < nums.size(); ++cur)if(nums[cur]) // 處理 非0 元素swap(nums[++dest], nums[cur]);}
};/*
- 時間復雜度：O(n)
- 空間復雜度：O(1)
*/

---

2. 復寫零

---

算法原理

代碼編寫

class Solution 
{
public:void duplicateZeros(vector<int>& nums) {// 1、初始化int dest = -1, cur = 0, n = nums.size();// 2、找到最后一個復寫的數while(true){if(nums[cur]) dest += 1;else dest += 2;if(dest >= n - 1) break;++cur;}cout << nums[cur] << endl;// 1.5、預處理 -> 讓 dest 的下標有效if(dest == n){if(nums[cur]) --cur, --dest;else {nums[n - 1] = 0;dest -= 2;cur -= 1;}}// 2、雙指針從后往前進行復寫操作while(cur >= 0){if(nums[cur]) nums[dest--] = nums[cur--];else{nums[dest--] = 0;nums[dest--] = 0;cur--;} }}
};
/*
- 時間復雜度：O(n)
- 空間復雜度：O(1)
*/

---

3. 快樂數

---

算法原理

代碼編寫

class Solution 
{
private:// 計算每個位置上的數字的平方和inline static int BitSum(int num){int ret = 0;while(num){int t = num % 10;ret += t * t;num /= 10;}return ret;}public:bool isHappy(int n) {int slow = n, fast = BitSum(n);while(slow != fast){slow = BitSum(slow);fast = BitSum(BitSum(fast));}return slow == 1;}
};

---

4. 盛最多水的容器

---

算法原理

代碼編寫

class Solution 
{
public:int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1;int ret = INT_MIN;while(left != right){// 容積 = 長度 * 高度int v = (right - left) * min(height[left], height[right]);ret = max(ret, v);// 移動指針 - 誰小移動誰height[left] < height[right] ? ++left : --right;}return ret;}
};
/*
- 時間復雜度：O(n)
- 空間復雜度：O(1)
*/

---

5. 有效三角形的個數

---

算法原理

代碼編寫

class Solution 
{
public:int triangleNumber(vector<int>& nums) {// 1、優化sort(nums.begin(), nums.end());// 2、利用雙指針解決問題int ret = 0, n = nums.size();for(int i = n - 1; i >= 2; --i){int left = 0, right = i - 1;while(left < right){// 當 a+b>c ，a下標屬于 [left, right-1]時，都能和 b、c 構成三角形// 當 a+b<=c ，b下標屬于[left-1, right]時，都不能和 a、c 構成三角形if(nums[left] + nums[right] > nums[i]){ret += right - left;--right;}else ++left;}}// 返回值return ret;}
};/*
- 時間復雜度：O(n^2)
- 空間復雜度：O(1)
*/

---

6. 查找總價格為目標值的兩個商品

---

算法原理

代碼編寫

class Solution 
{
public:vector<int> twoSum(vector<int>& price, int target) {// 1、數據初始化int left = 0, right = price.size() - 1;// 2、利用雙指針解決問題while(left < right){int sum = price[left] + price[right];if(sum < target) ++left;else if(sum > target) --right;else return {price[left], price[right]};}// 題目沒有明確說明沒有結果的話會怎么樣，那么該題的測試用例應該都是有結果的// 為了照顧編譯器要求一定要返回一個結果，所以我們最后返回一個空數組即可return {};}
};
/*
- 時間復雜度：O(n)
- 空間復雜度：O(1)
*/

---

7. 三數之和

---

算法原理

代碼編寫

class Solution 
{
public:vector<vector<int>> threeSum(vector<int>& nums) {// 1、初始化int n = nums.size();vector<vector<int>> ret;// 2、排序sort(nums.begin(), nums.end());// 3、依次固定一個數for(int i = 0; i < n - 2;){// 4、雙指針算法找到兩數之和等于 aim 的元素int left = i + 1, right = n - 1, aim = -nums[i];while(left < right){int sum = nums[left] + nums[right];if(sum < aim) ++left;else if(sum > aim) --right;else {ret.push_back( {nums[i], nums[left], nums[right]} );++left, --right; // 保證 left、right 選擇的元素不漏// 對 left、right 已經選擇過的元素去重while(left < right && nums[left] == nums[left - 1]) ++left;while(left < right && nums[right] == nums[right + 1]) --right;}}// 保證 i 選擇的元素不漏++i; // 對 i 已經選擇過的元素去重while(i < n - 2 && nums[i] == nums[i - 1]) ++i;}// 5、返回最終結果return ret;}
};
/*
- 時間復雜度：O(n^2)
- 空間復雜度：O(1)
*/

---

8. 四數之和

---

算法原理

代碼編寫

class Solution 
{
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {// 1、初始化int n = nums.size();vector< vector<int> > ret;// 2、排序sort(nums.begin(), nums.end());// 3、依次固定一個數，然后使用“三數之和”解決問題for(int i = 0; i < n - 3;) {// 4、再依次固定一個數，然后使用“雙指針”解決問題for(int j = i + 1; j < n - 2;) {int left = j + 1, right = n - 1;double aim = (double)target - nums[i] - nums[j];// 5、雙指針算法找到兩數之和等于 aim 的元素while(left < right){double sum = nums[left] + nums[right];if(sum < aim) ++left;else if(sum > aim) --right;else{ret.push_back( {nums[i], nums[j], nums[left], nums[right]} );++left, --right; // 保證 left、right 選擇的元素不漏// 對 left、right 已經選擇過的元素去重while(left < right && nums[left] == nums[left - 1]) ++left;while(left < right && nums[right] == nums[right + 1]) --right;}}// 保證 j 選擇的元素不漏++j;// 對 j 已經選擇過的元素去重while(j < n - 2 && nums[j] == nums[j - 1]) ++j;}// 保證 i 選擇的元素不漏++i;// 對 i 已經選擇過的元素去重while(i < n - 3 && nums[i] == nums[i - 1]) ++i;}// 6、返回最終結果return ret;}
};
/*
- 時間復雜度：O(n^3)
- 空間復雜度：O(1)
*/

專題二：滑動窗口

---

1. 長度最小的子數組

---

算法原理

代碼編寫

class Solution 
{
public:int minSubArrayLen(int target, vector<int>& nums) {// 1、初始化int n = nums.size();int minLength = INT_MAX;// 2、使用滑動窗口解決問題for(int left = 0, right = 0, sum = nums[0]; right < n;){if(sum >= target) {minLength = min(minLength, right - left + 1);sum -= nums[left++];}else {if(++right < n)sum += nums[right];}}// 3、返回值return minLength == INT_MAX ? 0 : minLength;}
};
/*
- 時間復雜度：O(n)
- 空間復雜度：O(1)
*/

---

2. 無重復字符的最長字串

---

算法原理

代碼編寫

class Solution 
{
public:int lengthOfLongestSubstring(string s) {// 1、初始化int n = s.size();vector<int> count(256);int left = 0, right = 0, ret = 0;// 2、滑動窗口int length = 0; //用來記錄窗口長度while(right < n){if(!count[s[right]]) //進窗口{++count[s[right]];++length;++right;ret = max(ret, length); //更新結果}else //出窗口{--count[s[left]];--length;++left;}}// 3、返回值return ret;}
};
/*
- 時間復雜度：O(n)
- 空間復雜度：O(1)
*/

---

3. 最大連續1的個數 III

---

算法原理

代碼編寫

class Solution 
{
public:int longestOnes(vector<int>& nums, int k) {// 1、初始化int n = nums.size();int ret = INT_MIN;// 2、滑動窗口int left = 0, right = 0;int length = 0; // 當前子數組中最長連續 1 的長度int zero = 0;  // 當前子數組中 0 出現的次數while(right < n){if(nums[right] != 0) // nums[right] 非 0，此時 right 一定入窗口{ret = max(ret, ++length);++right;}else{if(zero + 1 <= k) {ret = max(ret, ++length);++zero;++right;}else{if(nums[left++] == 0)  --zero;--length;}}}// 3、返回值return ret;}
};
/*
- 時間復雜度：O(n)
- 空間復雜度：O(1)
*/

---

4. 將 x 減到 0 的最小操作數

---

---

題目解析

---

算法原理

---

代碼編寫

class Solution 
{
public:int minOperations(vector<int>& nums, int x) {// 1、初始化int sum = 0;for(const auto e : nums) sum += e;int target = sum - x;// 2、細節處理(數組中所有元素都大于0，所以 target 小于 0 是不存在的)if(target < 0) return -1;// 3、滑動窗口int ret = -1;for(int left = 0, right = 0, tmp = 0; right < nums.size();){// 進窗口tmp += nums[right++];// 出窗口while(tmp > target) tmp -= nums[left++];// 更新結果if(tmp == target) ret = max(ret, right - left);}// 4、返回結果return ret == -1 ? ret : nums.size() - ret;}
};
/*
- 時間復雜度：O(n)
- 空間復雜度：O(1)
*/