15題: 三數之和
給你一個整數數組 nums ，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i != j、i != k 且 j != k ，同時還滿足 nums[i] + nums[j] + nums[k] == 0 。請
你返回所有和為 0 且不重復的三元組。
注意: 答案中不可以包含重復的三元組。
【思路1】
首先對數組進行排序題目等效于： 求 X + Y + Z = 0 ， X ！= Y ！= Z 而且數組中元素又不可以重復， 那么我們可以認為 三個元素的大小順序 就是 X <= Y <= Z 那么可以理解 ， X 就是3個元素中，最小的， 如果存在，則一定滿足
X <= 0 , 且 Z >= 0 并且當 X= 0 ， 那么一定是 Y=0，且 Z=0 這一種情況。那么可以根據 X+Y 的值 去Z中找 Z = -（X+Y）在第2層for循環中，利用二分查找，進行優化，而不是開啟第三層for循環。（如果第三層直接 for循環， 則會超時~）
解答:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;/*** 給你一個整數數組 nums ，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i != j、i != k 且 j != k ，同時還滿足 nums[i] + nums[j] + nums[k] == 0 。請* <p>* 你返回所有和為 0 且不重復的三元組。*/
public class Solution {// 第3層循環改為2分查找public List<List<Integer>> threeSum(int[] nums) {// 默認 x , y, z 由小到大List<List<Integer>> list = new ArrayList<>();// 1. 對數組進行排序Arrays.sort(nums);// 2. 進行遍歷for (int i = 0; i < nums.length; i++) {// 如果x>0,則直接結束for循環if (nums[i] > 0) {break;}if (i >= 1 && nums[i] == nums[i - 1]) {continue;}for (int j = i + 1; j < nums.length; j++) {if (j >= 2 && (j - 1 > i) && nums[j] == nums[j - 1]) {continue;}// 用二分查找, 查找是否存在 值為 -(nums[i]+nums[j]) 的值// 初始下標 k=j+1 , 終止下標: k=nums.length-1 , 且有序int start = j+1 ;int end = nums.length-1;int index = twoSplitSearch(nums, start, end, -(nums[i] + nums[j]));if (index<0){continue;}List<Integer> integers = Arrays.asList(nums[i], nums[j], nums[index]);list.add(integers);}}return list;}// 二分查找public static int twoSplitSearch(int[] ints,int startIndex, int endIndex,int target ){int result = -1;if (startIndex>endIndex){return result;}int mid = (startIndex+endIndex)/2;while (ints[mid]!=target && startIndex<endIndex){if (target > ints[mid]){startIndex=mid+1;}else {endIndex=mid-1;}mid=(startIndex+ endIndex)/2;}if (ints[mid]==target && mid>=startIndex){result=mid;}return result;}
}
自己記錄這個解法也只是剛剛通過, 還是很慢, 后面再更新更好的解法。
------------------ 更新-------------------------2024-07-07 --------------------------
【思路3】
同樣借助上面思路1的思想， 如果我們對僅僅根據 X 去找另外的2個值 Y， Z， 那樣就只要一個for循環，利用雙指針的思想。同樣，當 X > 0 即可結束最外層的for循環。如圖所示：
public class Solution {public static void main(String[] args) {Solution solution = new Solution();List<List<Integer>> list = solution.threeSum(new int[]{-4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6});System.out.println(list);}// 時間復雜度是 o(n^2)public List<List<Integer>> threeSum(int[] nums) {// 默認 x , y, z 由小到大List<List<Integer>> list = new ArrayList<>();// 1. 對數組進行排序Arrays.sort(nums);// 2. 進行遍歷for (int i = 0; i < nums.length; i++) {// 如果x>0,則直接結束for循環if (nums[i] > 0) {break;}if (i >= 1 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;int right = nums.length - 1;while (left < right) {int total = nums[left] + nums[right];// 去重判斷if (left - 1 > i && nums[left - 1] == nums[left]) {left++;continue;}// 去重判斷if (right < nums.length - 1 && nums[right] == nums[right + 1]) {right--;continue;}if (total == -nums[i]) {// 采集結果List<Integer> result = new ArrayList<>();result.add(nums[i]);result.add(nums[left]);result.add(nums[right]);list.add(result);// 那下一步到底是移動左還是右呢?// 嘗試左移?// 嘗試右移?// 直接左移有指針, 或者右移左指針都可以
// left++;right--;} else if (total > -nums[i]) {right--;} else {left++;}}}return list;}
}
到此結束 ~~~
