目錄
1.前言
2.正文
2.1快樂數
2.2盛最多水的容器
2.3有效的三角形的個數
2.4和為s的兩個數
2.5三數之和
2.6四數之和
3.小結
1.前言
哈嘍大家好吖，今天繼續加練算法題目，一共六道雙指針，希望能對大家有所幫助，廢話不多說讓我們開始吧。
2.正文
2.1快樂數
202. 快樂數 - 力扣（LeetCode）
https://leetcode.cn/problems/happy-number/description/
方法一：
public int happy(int n){int res = 0;while(n != 0){res += (n % 10) * (n % 10);n /= 10;}return res;}public boolean isHappy(int n) {HashSet <Integer> set = new HashSet<>();int ans = n;while(true){ans = happy(ans);if(ans == 1){return true;}if(set.contains(ans)){return false;}set.add(ans);}}代碼分析
happy?方法：
該方法的作用是計算一個整數?
n?的每個數字的平方和。通過?
n % 10?獲取?n?的最后一位數字，然后將其平方并累加到?res?中。通過?
n /= 10?去掉?n?的最后一位數字。循環直到?
n?變為 0，最后返回?res。
isHappy?方法：
該方法用于判斷一個整數?
n?是否為快樂數。使用一個?
HashSet?來記錄已經出現過的數字，用于檢測是否進入了循環。通過?
happy?方法計算?n?的平方和，并將結果存儲在?ans?中。如果?
ans?等于 1，說明?n?是快樂數，返回?true。如果?
ans?已經存在于?HashSet?中，說明進入了循環，返回?false。否則，將?
ans?添加到?HashSet?中，并繼續循環。核心思路總結
計算平方和：通過?
happy?方法計算一個數的每個數字的平方和。檢測循環：通過?
HashSet?記錄已經出現過的數字，如果某個數字重復出現，說明進入了循環，該數不是快樂數。終止條件：如果平方和最終為 1，則該數是快樂數。
?方法二：
public int bitSquareSum(int n) {int sum = 0;while(n > 0){int bit = n % 10;sum += bit * bit;n = n / 10;}return sum;}public boolean isHappy(int n) {int slow = n, fast = n;do{slow = bitSquareSum(slow);fast = bitSquareSum(fast);fast = bitSquareSum(fast);}while(slow != fast);return slow == 1;}?代碼分析
bitSquareSum?方法：
該方法的作用是計算一個整數?
n?的每個數字的平方和。通過?
n % 10?獲取?n?的最后一位數字，然后將其平方并累加到?sum?中。通過?
n /= 10?去掉?n?的最后一位數字。循環直到?
n?變為 0，最后返回?sum。
isHappy?方法：
該方法用于判斷一個整數?
n?是否為快樂數。使用快慢指針的思想：
slow?和?fast?初始都指向?n。
slow?每次調用一次?bitSquareSum，相當于每次走一步。
fast?每次調用兩次?bitSquareSum，相當于每次走兩步。如果?
slow?和?fast?相遇（即?slow == fast），說明存在循環。如果相遇時的值為 1，說明是快樂數；否則，不是快樂數。
核心思路總結
計算平方和：
通過?
bitSquareSum?方法計算一個數的每個數字的平方和。快慢指針檢測循環：
使用快慢指針的思想來檢測是否進入了循環。
如果快慢指針相遇，說明存在循環。
如果相遇時的值為 1，說明是快樂數；否則，不是快樂數。
空間優化：
相比于使用?
HashSet?的方法，快慢指針方法不需要額外的空間，空間復雜度為 O(1)。
2.2盛最多水的容器
11. 盛最多水的容器 - 力扣（LeetCode）https://leetcode.cn/problems/container-with-most-water/description/
方法一：
public int maxArea(int[] height) {int i = 0,j = height.length - 1;int area = 0;while(i != j){area = Math.max(area(i,j,height),area);if((height[j] - height[i]) <= 0)j--;else i++;}return area;}public int area(int a,int b,int[] height){return Math.min(height[a],height[b]) * Math.abs(b - a);}代碼分析
area?方法：
該方法的作用是計算兩條線之間的容器的面積。
面積的計算公式為：
面積 = 兩條線的最小高度 * 兩條線之間的距離。使用?
Math.min(height[a], height[b])?獲取兩條線的最小高度。使用?
Math.abs(b - a)?獲取兩條線之間的距離。返回計算得到的面積。
maxArea?方法：
該方法用于找到可以容納最多水的容器。
使用雙指針的方法：
初始化兩個指針?
i?和?j，分別指向數組的起始位置和末尾位置。初始化?
area?為 0，用于記錄當前的最大面積。在?
while?循環中：
計算當前指針?
i?和?j?之間的面積，并更新?area?為當前面積和歷史最大面積中的較大值。移動指針：
如果?
height[j] <= height[i]，則移動右指針?j--（因為左邊的線可能更高，可以嘗試找到更高的線）。否則，移動左指針?
i++（因為右邊的線可能更高，可以嘗試找到更高的線）。當?
i == j?時，循環結束，返回?area。
核心思路總結
雙指針法：
使用兩個指針?
i?和?j，分別指向數組的起始位置和末尾位置。通過移動指針來縮小搜索范圍，同時計算當前指針之間的面積。
面積計算：
容器的面積由兩條線的最小高度和它們之間的距離決定。
面積公式：
面積 = min(height[i], height[j]) * (j - i)。指針移動策略：
每次移動高度較小的指針，因為移動高度較大的指針不會增加面積（面積受限于較小的高度）。
通過這種方式，可以逐步縮小搜索范圍，同時確保不會錯過最大面積。
?方法二：
public int maxArea(int[] height) {int i = 0, j = height.length - 1, res = 0;while(i < j) {res = height[i] < height[j] ?Math.max(res, (j - i) * height[i++]):Math.max(res, (j - i) * height[j--]);}return res;}代碼分析
初始化：
使用兩個指針?
i?和?j，分別指向數組的起始位置和末尾位置。初始化?
res?為 0，用于記錄當前的最大面積。雙指針循環：
在?
while?循環中，當?i < j?時，執行以下操作：
如果?
height[i] < height[j]：
計算當前指針?
i?和?j?之間的面積：(j - i) * height[i]。更新?
res?為當前面積和歷史最大面積中的較大值。移動左指針?
i++（因為左邊的線較短，移動右指針不會增加面積）。否則：
計算當前指針?
i?和?j?之間的面積：(j - i) * height[j]。更新?
res?為當前面積和歷史最大面積中的較大值。移動右指針?
j--（因為右邊的線較短，移動左指針不會增加面積）。返回結果：
當?
i >= j?時，循環結束，返回?res。
核心思路總結
雙指針法：
使用兩個指針?
i?和?j，分別指向數組的起始位置和末尾位置。通過移動指針來縮小搜索范圍，同時計算當前指針之間的面積。
面積計算：
容器的面積由兩條線的最小高度和它們之間的距離決定。
面積公式：
面積 = min(height[i], height[j]) * (j - i)。指針移動策略：
每次移動高度較小的指針，因為移動高度較大的指針不會增加面積（面積受限于較小的高度）。
通過這種方式，可以逐步縮小搜索范圍，同時確保不會錯過最大面積。
2.3有效的三角形的個數
611. 有效三角形的個數 - 力扣（LeetCode）https://leetcode.cn/problems/valid-triangle-number/description/
方法一：
public int triangleNumber(int[] nums) {int ans = 0;Arrays.sort(nums);for(int i = 0;i < nums.length;i++){for(int j = i + 1;j < nums.length;j++){int left = j + 1,right = nums.length - 1,k = j;while (left <= right) {int mid = (left + right)/2;if(nums[i] + nums[j] > nums[mid]){k = mid;left = mid + 1;}else{right = mid - 1;}}ans += k - j;}}return ans;}代碼分析
排序：
首先對數組?
nums?進行升序排序。排序的目的是為了方便后續使用雙指針或二分查找來優化查找過程。雙重循環：
使用雙重循環遍歷數組：
外層循環固定一個數?
nums[i]，作為三角形的第一條邊。內層循環固定第二個數?
nums[j]，作為三角形的第二條邊。二分查找：
對于固定的?
nums[i]?和?nums[j]，使用二分查找來確定滿足?nums[i] + nums[j] > nums[k]?的最大?k。初始化?
left = j + 1?和?right = nums.length - 1，表示搜索范圍。在?
while?循環中：
計算中間位置?
mid = (left + right) / 2。如果?
nums[i] + nums[j] > nums[mid]，說明?mid?滿足條件，嘗試向右擴展范圍（left = mid + 1）。否則，向左縮小范圍（
right = mid - 1）。最終，
k?記錄的是滿足條件的最大下標。統計有效三元組：
對于固定的?
nums[i]?和?nums[j]，滿足條件的?k?的范圍是?[j + 1, k]，共有?k - j?個有效的三元組。將?
k - j?累加到結果?ans?中。返回結果：
最終返回?
ans，即所有有效三元組的個數。
核心思路總結
排序：
對數組進行排序，使得后續的查找過程更加高效。
雙重循環 + 二分查找：
外層循環固定第一條邊，內層循環固定第二條邊。
對于固定的兩條邊，使用二分查找確定滿足條件的第三條邊的最大下標。
三角形判定條件：
對于排序后的數組，如果?
nums[i] + nums[j] > nums[k]，則?nums[i] + nums[k] > nums[j]?和?nums[j] + nums[k] > nums[i]?也一定成立（因為數組已排序）。因此，只需要檢查?
nums[i] + nums[j] > nums[k]?即可。統計有效三元組：
對于固定的?
nums[i]?和?nums[j]，滿足條件的?k?的范圍是?[j + 1, k]，共有?k - j?個有效的三元組。
方法二：
public int triangleNumber(int[] nums) {int ans = 0;Arrays.sort(nums);for(int i = 0;i < nums.length;i++){int k = i + 1;for(int j = i + 1;j <nums.length;j++){while(k + 1 < nums.length && nums[k + 1] < nums[i] + nums[j]){k++;}ans += Math.max(k - j,0);}}return ans;}代碼分析
排序：
首先對數組?
nums?進行升序排序。排序的目的是為了方便后續使用雙指針來優化查找過程。雙重循環：
使用雙重循環遍歷數組：
外層循環固定一個數?
nums[i]，作為三角形的第一條邊。內層循環固定第二個數?
nums[j]，作為三角形的第二條邊。雙指針查找：
對于固定的?
nums[i]?和?nums[j]，使用雙指針的方法來確定滿足?nums[i] + nums[j] > nums[k]?的最大?k。初始化?
k = i + 1，表示第三條邊的起始位置。在?
while?循環中：
如果?
k + 1 < nums.length?且?nums[k + 1] < nums[i] + nums[j]，則移動右指針?k++。這樣，
k?會指向滿足條件的最大下標。最終，滿足條件的?
k?的范圍是?[j + 1, k]，共有?k - j?個有效的三元組。統計有效三元組：
對于固定的?
nums[i]?和?nums[j]，滿足條件的?k?的范圍是?[j + 1, k]，共有?k - j?個有效的三元組。將?
k - j?累加到結果?ans?中。返回結果：
最終返回?
ans，即所有有效三元組的個數。
核心思路總結
排序：
對數組進行排序，使得后續的查找過程更加高效。
雙重循環 + 雙指針：
外層循環固定第一條邊，內層循環固定第二條邊。
對于固定的兩條邊，使用雙指針確定滿足條件的第三條邊的最大下標。
三角形判定條件：
對于排序后的數組，如果?
nums[i] + nums[j] > nums[k]，則?nums[i] + nums[k] > nums[j]?和?nums[j] + nums[k] > nums[i]?也一定成立（因為數組已排序）。因此，只需要檢查?
nums[i] + nums[j] > nums[k]?即可。統計有效三元組：
對于固定的?
nums[i]?和?nums[j]，滿足條件的?k?的范圍是?[j + 1, k]，共有?k - j?個有效的三元組。
2.4和為s的兩個數
和為S的兩個數字__牛客網和為S的兩個數字 ,“一戰通offer”互聯網實習季編程挑戰模擬卷 https://www.nowcoder.com/questionTerminal/390da4f7a00f44bea7c2f3d19491311b
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {ArrayList<Integer> ans = new ArrayList<>();int i = 0,j = array.length - 1;while(i < j){if(array[i] + array[j] == sum){ans.add(array[i]);ans.add(array[j]);return ans;}else if(array[i] + array[j] > sum){j--;}else if(array[i] + array[j] < sum){i++;}}return ans;}?代碼分析
初始化：
使用一個?
ArrayList<Integer>?來存儲結果。使用兩個指針?
i?和?j，分別指向數組的起始位置和末尾位置。雙指針查找：
在?
while?循環中，當?i < j?時，執行以下操作：
如果?
array[i] + array[j] == sum：
將?
array[i]?和?array[j]?添加到結果列表?ans?中。返回結果列表?
ans。如果?
array[i] + array[j] > sum：
移動右指針?
j--（因為數組是有序的，右邊的數較大，移動右指針可以減小和）。如果?
array[i] + array[j] < sum：
移動左指針?
i++（因為數組是有序的，左邊的數較小，移動左指針可以增大和）。返回結果：
如果找到滿足條件的兩個數，直接返回結果列表。
如果循環結束后仍未找到滿足條件的兩個數，返回空的?
ans。
核心思路總結
雙指針法：
使用兩個指針?
i?和?j，分別指向數組的起始位置和末尾位置。通過移動指針來縮小搜索范圍，同時計算當前指針指向的兩個數的和。
數組有序性：
數組是有序的，因此可以通過比較?
array[i] + array[j]?與?sum?的大小關系來決定移動哪個指針。如果和大于?
sum，移動右指針；如果和小于?sum，移動左指針。返回結果：
如果找到滿足條件的兩個數，直接返回結果。
如果未找到滿足條件的兩個數，返回空列表。
2.5三數之和
15. 三數之和 - 力扣（LeetCode）https://leetcode.cn/problems/3sum/description/
public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> list = new ArrayList<>();Arrays.sort(nums);int n = nums.length;for(int i = 0;i < n;i++){if(i > 0 && nums[i - 1] == nums[i]){continue;}int left = i + 1;int right = n - 1;int target = -nums[i];while(left < right){int sum = nums[left] + nums[right];if(sum == target){list.add(Arrays.asList(nums[i],nums[left],nums[right]));left++;right--;while(left < right && nums[left] == nums[left - 1])left++;while(left < right && nums[right] == nums[right + 1])right--;}else if(sum < target){left++;}else{right--;}}}return list;}?代碼分析
排序：
首先對數組?
nums?進行升序排序。排序的目的是為了方便后續使用雙指針來優化查找過程，并且可以方便地跳過重復的元素。外層循環：
使用一個外層循環遍歷數組，固定一個數?
nums[i]?作為三元組的第一個數。如果?
nums[i]?與前一個數?nums[i - 1]?相同，則跳過當前循環（避免重復的三元組）。雙指針查找：
對于固定的?
nums[i]，使用雙指針的方法在剩余的子數組中查找兩個數?nums[left]?和?nums[right]，使得?nums[i] + nums[left] + nums[right] = 0。初始化?
left = i + 1?和?right = n - 1，表示搜索范圍。在?
while?循環中：
計算當前的和?
sum = nums[left] + nums[right]。如果?
sum == target（即?sum == -nums[i]）：
將?
[nums[i], nums[left], nums[right]]?添加到結果列表?list?中。移動左指針?
left++?和右指針?right--。跳過重復的?
nums[left]?和?nums[right]，避免重復的三元組。如果?
sum < target：
移動左指針?
left++（因為數組是有序的，左邊的數較小，移動左指針可以增大和）。如果?
sum > target：
移動右指針?
right--（因為數組是有序的，右邊的數較大，移動右指針可以減小和）。返回結果：
最終返回結果列表?
list，其中包含所有滿足條件的不重復三元組。
核心思路總結
排序：
對數組進行排序，使得后續的查找過程更加高效，并且可以方便地跳過重復的元素。
外層循環 + 雙指針：
外層循環固定第一個數?
nums[i]。對于固定的?
nums[i]，使用雙指針在剩余的子數組中查找兩個數?nums[left]?和?nums[right]，使得?nums[i] + nums[left] + nums[right] = 0。跳過重復元素：
在外層循環中，如果?
nums[i]?與前一個數?nums[i - 1]?相同，則跳過當前循環。在雙指針查找過程中，如果?
nums[left]?或?nums[right]?與下一個數相同，則跳過重復的數。結果存儲：
將滿足條件的三元組?
[nums[i], nums[left], nums[right]]?添加到結果列表?list?中。
2.6四數之和
18. 四數之和 - 力扣（LeetCode）https://leetcode.cn/problems/4sum/description/
?
public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> ans = new ArrayList<>();Arrays.sort(nums);int n = nums.length;for (int i = 0; i < n - 3; i++) {if (i > 0 && nums[i] == nums[i - 1]) continue;for (int j = i + 1; j < n - 2; j++) {if (j > i + 1 && nums[j] == nums[j - 1]) continue;int l = j + 1, r = n - 1;long aim = (long) target - nums[i] - nums[j];while (l < r) {long sum = (long) nums[l] + nums[r];if (sum == aim) {ans.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));l++;r--;while (l < r && nums[l] == nums[l - 1]) l++;while (l < r && nums[r] == nums[r + 1]) r--;} else if (sum < aim) {l++;} else {r--;}}}}return ans;}?代碼分析
排序：
首先對數組?
nums?進行升序排序。排序的目的是為了方便后續使用雙指針來優化查找過程，并且可以方便地跳過重復的元素。雙重循環：
使用雙重循環遍歷數組：
外層循環固定一個數?
nums[i]，作為四元組的第一個數。內層循環固定第二個數?
nums[j]，作為四元組的第二個數。在每次循環中，如果當前數與前一個數相同，則跳過當前循環（避免重復的四元組）。
雙指針查找：
對于固定的?
nums[i]?和?nums[j]，使用雙指針的方法在剩余的子數組中查找兩個數?nums[l]?和?nums[r]，使得?nums[i] + nums[j] + nums[l] + nums[r] = target。初始化?
l = j + 1?和?r = n - 1，表示搜索范圍。計算目標值?
aim = target - nums[i] - nums[j]。在?
while?循環中：
計算當前的和?
sum = nums[l] + nums[r]。如果?
sum == aim：
將?
[nums[i], nums[j], nums[l], nums[r]]?添加到結果列表?ans?中。移動左指針?
l++?和右指針?r--。跳過重復的?
nums[l]?和?nums[r]，避免重復的四元組。如果?
sum < aim：
移動左指針?
l++（因為數組是有序的，左邊的數較小，移動左指針可以增大和）。如果?
sum > aim：
移動右指針?
r--（因為數組是有序的，右邊的數較大，移動右指針可以減小和）。返回結果：
最終返回結果列表?
ans，其中包含所有滿足條件的不重復四元組。
核心思路總結
排序：
對數組進行排序，使得后續的查找過程更加高效，并且可以方便地跳過重復的元素。
雙重循環 + 雙指針：
外層循環固定第一個數?
nums[i]，內層循環固定第二個數?nums[j]。對于固定的?
nums[i]?和?nums[j]，使用雙指針在剩余的子數組中查找兩個數?nums[l]?和?nums[r]，使得?nums[i] + nums[j] + nums[l] + nums[r] = target。跳過重復元素：
在外層循環和內層循環中，如果當前數與前一個數相同，則跳過當前循環。
在雙指針查找過程中，如果?
nums[l]?或?nums[r]?與下一個數相同，則跳過重復的數。結果存儲：
將滿足條件的四元組?
[nums[i], nums[j], nums[l], nums[r]]?添加到結果列表?ans?中。
3.小結
今天的分享到這里就結束了，喜歡的小伙伴點點贊點點關注，你的支持就是對我最大的鼓勵，大家加油！
