前言

朋友們，大家好啊，從今天開始我將陸續為大家更新關于算法方面的文章，如果大家對于算法感興趣的話，歡迎大家訂閱我的算法專欄。

什么是雙指針算法

雙指針算法（Two Pointers Algorithm）是一種常用的算法技巧，通常用于數組、鏈表或其他線性數據結構中的問題。該算法使用兩個指針在數據結構上進行迭代、搜索或比較，以解決特定的問題。

在雙指針算法中，通常使用兩個指針分別稱為"快指針"和"慢指針"。快指針和慢指針起始位置通常相同，然后根據問題的要求，以不同的步長移動指針。快指針可能會每次移動多個位置，而慢指針則每次只移動一個位置。

雙指針算法有幾種常見的應用方式：

1. 對撞指針（Two Pointers Approach）：快指針從數組的首部開始，慢指針從數組的尾部開始，兩者向中間移動，直到它們相遇或交叉。這種方法通常用于有序數組中的搜索、求和等問題。

2. 快慢指針（Fast and Slow Pointers）：快指針和慢指針以不同的速度遍歷鏈表。這種方法通常用于解決鏈表中的環檢測、找到鏈表中點、鏈表的反轉等問題。

3. 滑動窗口（Sliding Window）：使用兩個指針在數組或字符串上定義一個固定大小的窗口，然后根據問題要求移動窗口的起始位置或結束位置。這種方法通常用于字符串或數組中的子串或子數組問題。

雙指針算法的優點在于它的時間復雜度通常較低，并且在遍歷數據時只需要常量級的額外空間。它可以有效地降低問題的時間復雜度，并且常常用于解決一些數組、鏈表相關的問題。

1.移動零

https://leetcode.cn/problems/move-zeroes/

1.1 題目要求

給定一個數組 nums，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。

請注意 ，必須在不復制數組的情況下原地對數組進行操作。

示例 1:

輸入: nums = [0,1,0,3,12]
輸出: [1,3,12,0,0]

示例 2:

輸入: nums = [0]
輸出: [0]

class Solution {public void moveZeroes(int[] nums) {}
}

1.2 做題思路

這個題目的目的就是將數組中的所有零給移動到非0數字的右邊部分，而我們使用雙指針就剛好可以將一個數組分為三部分，第一部分是非零部分，第二部分是數字0，第三部分是待移動的部分。

而這三個部分，我們使用兩個指針 slow 和 fast 來維護，當 fast 所指的數字不為 0 時，就與 slow 所指的數字進行交換。這樣就可以保證 slow 左邊是已經移動之后的非 0 數字，slow 與 fast 之間是移動之后的 0 數字，fast 右邊是待移動的部分。

1.3 Java代碼實現

class Solution {public void moveZeroes(int[] nums) {int slow = -1;int fast = 0;int n = nums.length;while(fast < n) {if(nums[fast] != 0) {int tmp = nums[++slow];nums[slow] = nums[fast];nums[fast] = tmp;}fast++;}}
}

2.復寫零

https://leetcode.cn/problems/duplicate-zeros/

2.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]

class Solution {public void duplicateZeros(int[] arr) {}
}

2.2 做題思路

很多人拿到這個題首先想的是從前往后使用雙指針，當遇到0的時候，將0寫兩次，但是如果這樣的話會將后面的數字給覆蓋，這就會顯得很麻煩。我們不妨換個思路：可以先找到復寫之后數組的最后一個數字，然后從后往前進行數據的寫入，當遇到0就寫兩次，非0就寫一次。

所以做這個題目大致分為兩步：1.找到復寫之后數組的最后一個數字 2.從后往前寫入數據

2.3 Java代碼實現

class Solution {public void duplicateZeros(int[] arr) {int slow = 0;int fast = -1;int n = arr.length;//1.找到復寫之后數組的最后一個數字while(fast < n-1) {if(arr[slow] != 0) fast++;else fast += 2;if(fast >= n-1) break;slow++;}//2.調整邊界//當fast=n的時候，說明slow所指的最后一個數字為0if(fast == n) {arr[n-1] = 0;fast = n-2;slow--;}//3.從后往前寫入數據while(slow >= 0) {if(arr[slow] != 0) {arr[fast--] = arr[slow--];}else {arr[fast--] = 0;arr[fast--] = 0;slow--;}}}
}

3.快樂數

https://leetcode.cn/problems/happy-number/

3.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

class Solution {public boolean isHappy(int n) {}
}

3.2 做題思路

要判斷是否為快樂數，我們需要知道，當我們進行每位數的平方和這個操作的時候，最終都會形成一個環。


既然都會形成環，那么我們只需要使用快慢指針來找到這個環，然后判斷這個環是否為1，如果是快樂數的話，他會在1->1之間形成環，而非快樂數就不一定了。

3.3 Java代碼實現

class Solution {private int bitSum(int n) {int sum = 0;while(n != 0) {int tmp = n % 10;sum += tmp*tmp;n /= 10;}return sum;}public boolean isHappy(int n) {int slow = n;int fast = bitSum(n); //這里先將快指針進行一次求和操作，防止剛開始就相等了//slow每次進行一次操作，fast一次進行兩次操作while(slow != fast) {slow = bitSum(slow);fast = bitSum(bitSum(fast));if(slow == fast) break;}return slow == 1;}
}

4.盛最多水的容器

https://leetcode.cn/problems/container-with-most-water/

4.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

class Solution {public int maxArea(int[] height) {}
}

4.2 做題思路

容器的容量跟 xy 的乘積有關，所以我們既需要考慮 x，也需要考慮 y，但是無法保證一上來 x 和 y 就是最大的，我們只能保證 x 或者 y 其中一個是最大的，然后再找 xy 最大的時候。所以這里我們先保證 x 是最大的，left 指針指向最左邊，right 指針指向最右邊，接著再找 x*y 乘積最大。

容積這樣計算 (right - left) * min(height[left],height[right])。設置一個變量來存放體積，并不斷更新這個變量，保證這個變量存儲的是容積最大的數據。left 和 right 的值也是需要不斷改變的，需要更換掉 left 和 right 所指向的數據較小的指針，因為我們要找的是乘積最大的數據。

• 容器的寬度?定變?。
• 由于左邊界較?，決定了?的?度。如果改變左邊界，新的???度不確定，但是?定不會超過右邊的柱??度，因此容器的容積可能會增?。
• 如果改變右邊界，?論右邊界移動到哪?，新的??的?度?定不會超過左邊界，也就是不會超過現在的???度，但是由于容器的寬度減?，因此容器的容積?定會變?的

4.3 Java代碼實現

class Solution {public int maxArea(int[] height) {int n = height.length;int left = 0;int right = n-1;int ret = 0;  //用來存儲體積while(left < right) {int v = (right - left) * Math.min(height[left],height[right]);ret = Math.max(v,ret);if(height[left] < height[right]) left++;else right--;}return ret;}
}

5.有效三角形的個數

https://leetcode.cn/problems/valid-triangle-number/

5.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

class Solution {public int triangleNumber(int[] nums) {}
}

5.2 做題思路

說的有效的三角形，大家應該都不陌生吧：任意兩邊之和大于第三邊，但是，我們真的需要兩兩組合都判斷一遍嗎，其實并不是的，只需要判斷兩個較短的邊之和大于較長的那個邊就可以了。

既然知道了只需要判斷一次就可以判斷是否是有效的三角形，所以我們可以先對數組進行一個升序排序，從數組的最后開始，將它作為三角形的最長的邊，然后在前面的數組范圍內，left 指針指向前面部分的最左邊，right 指針指向最右邊，通過移動 left 和right 的位置來統計有效三角形的個數。如果 nums[left] + nums[right} > 最長的邊，那么從 left 開始到 right - 1 的邊和 right、最長的邊都可以組合成一個有效的三角形；所以，以該長度為最長邊的三角形的個數為 right -left，然后right–，繼續該操作，直到left == right；如果 nums[left] + nums[right} < 最長的邊，就需要移動 left 的位置，直到遇到 nums[left] + nums[right} > 最長的邊 的位置，再統計有效三角形的個數。

5.3 Java代碼實現

class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int sum = 0;for(int i = nums.length-1; i > 1; i--) {int left = 0;int right = i-1;while(left < right) {if(nums[left] + nums[right] > nums[i]) {sum = sum + right - left;right--;}else {left++;}}}return sum;}
}

6.和為S的兩個數字

https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/

6.1 題目要求

輸入一個遞增排序的數組和一個數字s，在數組中查找兩個數，使得它們的和正好是s。如果有多對數字的和等于s，則輸出任意一對即可。

示例 1：

輸入：nums = [2,7,11,15], target = 9
輸出：[2,7] 或者 [7,2]
示例 2：

輸入：nums = [10,26,30,31,47,60], target = 40
輸出：[10,30] 或者 [30,10]

class Solution {public int[] twoSum(int[] nums, int target) {}
}

6.2 做題思路

這個題目的思路跟上面的思路差不多。使用雙指針，left 指向數組的最左邊（也就是最小值），right 指向數組的最右邊（最大值），然后判斷 nums[left] + nums[right] 跟target 的關系，如果 nums[left] + nums[right] > target ，就調整 right 的值；如果 nums[left] + nums[right] < target 就調整 left 的值，如果相等就存下來。

6.3 Java代碼實現

class Solution {public int[] twoSum(int[] nums, int target) {int left = 0;int right = nums.length-1;while(left < right) {int sum = nums[left] + nums[right];if(sum > target) {right--;}else if(sum < target) {left++;}else {return new int[]{nums[left],nums[right]};}}return new int[]{-1,-1};}
}

7.三數之和

https://leetcode.cn/problems/3sum/

7.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 。

class Solution {public List<List<Integer>> threeSum(int[] nums) {}
}

7.2 做題思路

當直到了如何解決兩數之和的問題之后，求三數值和其實也很簡單，還是現將數組以升序的方式排序我們每次固定一個數字，然后在剩下的數組中找到和為 target - nums[i] 的值，但是真的有這么簡單嗎？注意看題目，答案中不可出現重復的三元組，什么叫做重復的三元組，看第一個示例，它等于 target 的三個數有 (-1,0,1),(0,1,-1),(-1,2,-1) ，但是最終輸出的結果只有[[-1,-1,2],[-1,0,1]]，所以這道題關鍵難在去重這個問題上，那么我們應該如何去重呢？當調整 left、right 和那個固定的數字的時候，如果所指的數字等于前面的數字那么就跳過。

7.3 Java代碼實現

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> list = new ArrayList<>();Arrays.sort(nums);int n = nums.length;int i = 0;while(i < n && nums[i] <= 0) {int left = i + 1;int right = n - 1;int target = -nums[i];while(left < right) {int sum = nums[left] + nums[right];if(sum > target) {right--;}else if(sum < target) {left++;}else {List<Integer> list1 = new ArrayList<>();list1.add(nums[i]);list1.add(nums[left]);list1.add(nums[right]);list.add(list1);left++;right--;//去重并且防止越界while(left < right && nums[left] == nums[left-1]) left++;while(left < right && nums[right] == nums[right+1]) right--;}}i++;while(i < n && nums[i] <= 0 && nums[i] == nums[i-1]) i++;}return list;}
}

8.四數之和

https://leetcode.cn/problems/4sum/

8.1 題目要求

給你一個由 n 個整數組成的數組 nums ，和一個目標值 target 。請你找出并返回滿足下述全部條件且不重復的四元組 [nums[a], nums[b], nums[c], nums[d]] （若兩個四元組元素一一對應，則認為兩個四元組重復）：

0 <= a, b, c, d < n
a、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]]

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {}
}

8.2 做題思路

這個求四數之和，如果前面的兩數之和和三數之和會做了，這個題目也很簡單，我們只需要先固定一個數字，然后在后面的數組內找到和為 target - nums[i] 的三個數就行了，唯一需要注意的就是去重。那么這個題目我就不過多介紹了，大家直接看代碼就行了。

8.3 Java代碼實現

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> list = new ArrayList<>();int i = 0;int n = nums.length;Arrays.sort(nums);while(i < n) {int j = i + 1;long tmp1 = target-nums[i];while(j < n) {int slow = j + 1;int fast = n-1;long tmp2 = tmp1 - nums[j];while(slow < fast) {int sum = nums[slow] + nums[fast];if(sum > tmp2) {fast--;}else if(sum < tmp2) {slow++;}else {List<Integer> list1 = new ArrayList<>();list1.add(nums[i]);list1.add(nums[j]);list1.add(nums[slow]);list1.add(nums[fast]);list.add(list1);slow++;fast--;while(slow < fast && nums[slow] == nums[slow-1]) slow++;while(slow < fast && nums[fast] == nums[fast+1]) fast--;}}j++;while(j < n && nums[j] == nums[j-1]) j++;}i++;while(i < n && nums[i] == nums[i-1]) i++;}return list;}
}