引言：此專欄為記錄算法學習，本專題作為算法學習的第一部分，優選算法專題共計100題，分為不同小模塊進行，算法學習需堅持積累，時代不會辜負長期主義者，僅以此句，與君共勉。
講解算法分為三個步驟：(1) 題目分析 （2）算法原理 （3）代碼編寫
下面的所有題目講解都會以上述三個步驟開展
1. 移動零? ? ?283. 移動零 - 力扣（LeetCode）
(1) 題目分析：
給定一個數組 nums，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。
請注意?，必須在不復制數組的情況下原地對數組進行操作。?
示例 1:
輸入: nums = [0,1,0,3,12]
輸出: [1,3,12,0,0]
示例 2:
輸入: nums = [0]
輸出: [0]?
提示:
? 1 <= nums.length <= 104
? -231?<= nums[i] <= 231?- 1原地操作，將所有0移動到數組右側
示例 ：nums = [0,1,0,3,1,2]? ? ---> [1,3,1,2,0,0]
(2) 算法原理：（快排的思想：數組劃分區間 - 數組分兩塊）：
雙指針算法 -- 利用數組下標來充當指針?(這里我們定義兩個指針? ?cur , dest)兩個指針的作用：cur : 從左往右掃描數組，遍歷數組dest:? 已處理的區間內，非零元素的最后一個位置
如何做到：
1.cur 遇到0元素，cur++
2，遇到非0元素，swap(dest+1,cur);
dest++ ,cur++;
(3)代碼編寫
這里注意一下dest使用的是前置++還是后置++取決于dest的起始位置
class Solution { public:void moveZeroes(vector<int>& nums) {for(int cur = 0, dest = 0; cur < nums.size(); cur++)if(nums[cur]){swap(nums[dest++], nums[cur]); } } };class Solution { public:void moveZeroes(vector<int>& nums) {for(int cur = 0, dest = -1; cur < nums.size(); cur++)if(nums[cur]){swap(nums[++dest], nums[cur]); } } };這個?法是往后我們學習「快排算法」的時候，「數據劃分」過程的重要?步。如果將快排算法拆 解的話，這?段?代碼就是實現快排算法的「核?步驟」。
2. 復寫零? ? ?1089. 復寫零 - 力扣（LeetCode）
(1）題目分析?
給你一個長度固定的整數數組?
arr?，請你將該數組中出現的每個零都復寫一遍，并將其余的元素向右平移。注意：請不要在超過該數組長度的位置寫入元素。請對輸入的數組?就地?進行上述修改，不要從函數返回任何東西。
示例 1：
輸入：arr = [1,0,2,3,0,4,5,0] 輸出：[1,0,0,2,3,0,0,4] 解釋：調用函數后，輸入的數組將被修改為：[1,0,0,2,3,0,0,4]示例 2：
輸入：arr = [1,2,3] 輸出：[1,2,3] 解釋：調用函數后，輸入的數組將被修改為：[1,2,3]這里我們要注意的問題是數組的長度是固定的，要復寫0，原數組里可能會有數據就不存在了，所以我們可以先找到復寫完的最后一個位置的元素，再從前往后完成復寫操作
（2）算法原理?
如果從前向后進行原地復寫操作的話，由于0的復寫操作，導致沒有復寫的數被覆蓋掉，因此我們選擇從后往前的復寫策略。
但是從后向前復寫的時候，我們需要找到最后一個復寫的數，大致分為兩步：
1. 先找到最后一個復寫的數
2.然后從后面向前進行復寫操作
流程：
先根據“異地”操作，然后優化成雙指針的“就地”操作
a. 先找到最后一個”復寫“的數：
? ? 1.先判斷cur位置的值
? ? 2.決dest移動兩步還是一步
? ? 3.判斷一下dest是否已經到結束為止
? ? 4.cur++
b.處理一下邊界情況
? ? n-1 ---> 0?
? ? cur?--;
? ? dest?-= 2;
c.從后向前完成復寫操作
示意圖：
（3）代碼編寫?
class Solution { public:void duplicateZeros(vector<int>& arr) {// 1. 先找到最后?個數int cur = 0, dest = -1, n = arr.size();while(cur < n){if(arr[cur]) dest++;else dest += 2;if(dest >= n - 1) break;cur++;}// 2. 處理?下邊界情況if(dest == n){arr[n - 1] = 0;cur--; dest -=2;}// 3. 從后向前完成復寫操作while(cur >= 0){if(arr[cur]) arr[dest--] = arr[cur--];else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}} };class Solution { public:void duplicateZeros(vector<int>& arr) {int n = arr.size();int i = 0, j = 0;// 第一遍掃描：計算復制后的新長度while (j < n) {if (arr[i] == 0) j++;i++;j++;}// 回退指針準備復制i--;j--;// 第二遍掃描：從后向前復制元素while (i >= 0) {if (j < n) arr[j] = arr[i];if (arr[i] == 0) {j--;if (j < n) arr[j] = 0;}i--;j--;}} };
3. 快樂數? ?? ? 202. 快樂數 - 力扣（LeetCode）
（1）題目分析
編寫一個算法來判斷一個數?
n?是不是快樂數。「快樂數」?定義為：
- 對于一個正整數，每一次將該數替換為它每個位置上的數字的平方和。
- 然后重復這個過程直到這個數變為 1，也可能是?無限循環?但始終變不到 1。
- 如果這個過程?結果為?1，那么這個數就是快樂數。
如果?
n?是?快樂數?就返回?true?；不是，則返回?false?。示例 1：
輸入：n = 19 輸出：true 解釋： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1示例 2：
輸入：n = 2 輸出：false
（2）算法原理
詳解：Leet code每日一題-CSDN博客
（3）代碼編寫?
class Solution { public:int squre_sum(int n){int sum = 0;while(n){int t = n %10;sum += t*t;n /= 10;}return sum;}bool isHappy(int n) {int slow = n,fast = squre_sum(n); while(slow != fast){slow = squre_sum(slow);fast = squre_sum(squre_sum(fast));}return slow == 1;} };
?4. 盛最多水的類型??? ? 11. 盛最多水的容器 - 力扣（LeetCode）
（1）題目分析?
給定一個長度為?
n?的整數數組?height?。有?n?條垂線，第?i?條線的兩個端點是?(i, 0)?和?(i, height[i])?。找出其中的兩條線，使得它們與?
x?軸共同構成的容器可以容納最多的水。返回容器可以儲存的最大水量。
說明：你不能傾斜容器。
示例 1：
輸入：[1,8,6,2,5,4,8,3,7] 輸出：49 解釋：圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為?49。示例 2：
輸入：height = [1,1] 輸出：1
（2）算法原理?
Leet code 每日一題-CSDN博客
（3）代碼編寫?
class Solution { public:int maxArea(vector<int>& height){int left = 0,right = height.size()-1,ret = 0;while(left < right){int v = min(height[left] , height[right])*(right - left);ret = max(ret , v);if(height[left] < height[right]) left++;else right--;}return ret;} };
5.有效三角形的個數? ? ?611. 有效三角形的個數 - 力扣（LeetCode）
（1）題目分析?
給定一個包含非負整數的數組?
nums?，返回其中可以組成三角形三條邊的三元組個數。示例 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
（2）算法原理?
Leet code 每日一題-CSDN博客
（3）代碼編寫???
class Solution { public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int ret = 0,n = nums.size();for(int i = n-1;i>=2;i--){int left = 0, right = i -1;while(left < right){if(nums[left] +nums[right] > nums[i]){ret += right -left;right--;}else{left++;}}}return ret;} };
6.和為S的兩個數LCR 179. 查找總價格為目標值的兩個商品 - 力扣（LeetCode）
（1）題目分析?
購物車內的商品價格按照升序記錄于數組?
price。請在購物車中找到兩個商品的價格總和剛好是?target。若存在多種情況，返回任一結果即可。示例 1：
輸入：price = [3, 9, 12, 15], target = 18 輸出：[3,15] 或者 [15,3]示例 2：
輸入：price = [8, 21, 27, 34, 52, 66], target = 61 輸出：[27,34] 或者 [34,27]
（2）算法原理?
解法?（暴?解法，會超時）：算法思路：兩層 for 循環列出所有兩個數字的組合，判斷是否等于?標值。算法流程：兩層 for 循環：?外層 for 循環依次枚舉第?個數 a ；?內層 for 循環依次枚舉第?個數 b ，讓它與 a 匹配；ps ：這?有個魔?細節：我們挑選第?個數的時候，可以不從第?個數開始選，因為 a 前?的數我們都已經在之前考慮過了；因此，我們可以從 a 往后的數開始列舉。?然后將挑選的兩個數相加，判斷是否符和目標值. 解法?（雙指針 - 對撞指針）：注意到本題是升序的數組，因此可以?「對撞指針」優化時間復雜度。算法流程（附帶算法分析，為什么可以使?對撞指針）：a. 初始化 left ， right 分別指向數組的左右兩端（這?不是我們理解的指針，?是數組的下標）b. 當 left < right 的時候，?直循環i. 當 nums[left] + nums[right] == target 時，說明找到結果，記錄結果，并且返回；ii. 當 nums[left] + nums[right] < target 時：?對于 nums[left] ??，此時 nums[right] 相當于是 nums[left] 能碰到的最?值（別忘了，這?是升序數組哈~）。如果此時不符合要求，說明在這個數組??，沒有別的數符合 nums[left] 的要求了（最?的數都滿?不了你，你已經沒救了）。因此，我們可以?膽舍去這個數，讓 left++ ，去?較下?組數據；?那對于 nums[right] ??，由于此時兩數之和是?于?標值的， nums[right]還可以選擇? nums[left] ?的值繼續努?達到?標值，因此 right 指針我們按兵不動；iii. 當 nums[left] + nums[right] > target 時，同理我們可以舍去nums[right] （最?的數都滿?不了你，你也沒救了）。讓 right-- ，繼續?較下?組數據，? left 指針不變（因為他還是可以去匹配? nums[right] 更?的數的）。
（3）代碼編寫??
class Solution { public:vector<int> twoSum(vector<int>& nums, int target){int left = 0, right = nums.size() - 1;while(left < right){int sum = nums[left] + nums[right];if(sum > target) right--;else if(sum < target) left++;else return {nums[left], nums[right]};}// 照顧編譯器return {-4941, -1};??????? } };
7. 三數之和?15. 三數之和 - 力扣（LeetCode）
（1）題目分析?
給你一個整數數組?
nums?，判斷是否存在三元組?[nums[i], nums[j], nums[k]]?滿足?i != j、i != k?且?j != k?，同時還滿足?nums[i] + nums[j] + nums[k] == 0?。請你返回所有和為?0?且不重復的三元組。注意：答案中不可以包含重復的三元組。
示例 1：
輸入：nums = [-1,0,1,2,-1,-4] 輸出：[[-1,-1,2],[-1,0,1]] 解釋： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元組是 [-1,0,1] 和 [-1,-1,2] 。 注意，輸出的順序和三元組的順序并不重要。示例 2：
輸入：nums = [0,1,1] 輸出：[] 解釋：唯一可能的三元組和不為 0 。示例 3：
輸入：nums = [0,0,0] 輸出：[[0,0,0]] 解釋：唯一可能的三元組和為 0 。
（2）算法原理?
解法（排序+雙指針）：
算法思路：本題與兩數之和類似，是?常經典的?試題。與兩數之和稍微不同的是，題?中要求找到所有「不重復」的三元組。那我們可以利?在兩數之和那??的雙指針思想，來對我們的暴?枚舉做優化：i. 先排序；ii. 然后固定?個數 a ：iii. 在這個數后?的區間內，使?「雙指針算法」快速找到兩個數之和等于 -a 即可。但是要注意的是，這道題??需要有「去重」操作~i. 找到?個結果之后， left 和 right 指針要「跳過重復」的元素；ii. 當使?完?次雙指針算法之后，固定的 a 也要「跳過重復」的元素。
（3）代碼編寫
class Solution { public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;// 1. 排序sort(nums.begin(), nums.end());// 2. 利?雙指針解決問題int n = nums.size();for(int i = 0; i < n; ) // 固定數 a{if(nums[i] > 0) break; // ?優化int left = i + 1, right = n - 1, target = -nums[i];while(left < right){int sum = nums[left] + nums[right];if(sum > target) right--;else if(sum < target) left++;else{ret.push_back({nums[i], nums[left], nums[right]});left++, right--;// 去重操作 left 和 rightwhile(left < right && nums[left] == nums[left - 1]) left++;while(left < right && nums[right] == nums[right + 1]) right--;}}// 去重 i i++;while(i < n && nums[i] == nums[i - 1]) i++;}return ret;} };
8.四數之和?18. 四數之和 - 力扣（LeetCode）
（1）題目分析?
給你一個由?
n?個整數組成的數組?nums?，和一個目標值?target?。請你找出并返回滿足下述全部條件且不重復的四元組?[nums[a], nums[b], nums[c], nums[d]]?（若兩個四元組元素一一對應，則認為兩個四元組重復）：
0 <= a, b, c, d?< na、b、c?和?d?互不相同nums[a] + nums[b] + nums[c] + nums[d] == target你可以按?任意順序?返回答案 。
示例 1：
輸入：nums = [1,0,-1,0,-2,2], target = 0 輸出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2：
輸入：nums = [2,2,2,2,2], target = 8 輸出：[[2,2,2,2]]
（2）算法原理?
.解法（排序 + 雙指針）算法思路：a. 依次固定?個數 a ；b. 在這個數 a 的后?區間上，利?「三數之和」找到三個數，使這三個數的和等于 target- a 即可
（3）代碼編寫??
class Solution { public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ret;// 1. 排序sort(nums.begin(), nums.end());// 2. 利?雙指針解決問題int n = nums.size();for(int i = 0; i < n; ) // 固定數 a{// 利? 三數之和for(int j = i + 1; j < n; ) // 固定數 b{// 雙指針int left = j + 1, right = n - 1;long long aim = (long long)target - nums[i] - nums[j];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[j], nums[left++], nums[right--]});// 去重?while(left < right && nums[left] == nums[left - 1]) left++;while(left < right && nums[right] == nums[right + 1]) right--;}}// 去重?j++;while(j < n && nums[j] == nums[j - 1]) j++;}// 去重三i++;while(i < n && nums[i] == nums[i - 1]) i++;}return ret;} };
