1.题目描述
2.思路
思路1:
补充:
break 和 continue 是 Java(以及其他编程语言)中控制循环流程的重要关键字
思路2:
先判断三数之和 sum 是正的、负的还是等于 0;
只有当 sum == 0 时才加入结果;
然后再分别跳过重复的 left 和 right。
3.代码实现
方法一:不推荐,超出时间限制。
时间复杂度是 O(n²),空间复杂度最坏是 O(n²),虽然逻辑清晰,但是性能比不上双指针法,特别是在数据量大的时候容易 超时或内存爆炸。
class Solution {public List<List<Integer>> threeSum(int[] nums) {int left=0;int right=nums.length-1;Set<List<Integer>> result=new HashSet<>();//结果集合,保存的是三元组(一个列表),不是整数Arrays.sort(nums);//对数组进行按升序排序for(int i=0;i<nums.length-2;i++)//i<nums.length-2倒数第三个元素{ Set<Integer> seen=new HashSet<>();int target=-nums[i]; // 在剩下的部分找两个数,使它们的和等于 -nums[i]for(int j=i+1;j<=nums.length-1;j++ ){int twochar=target-nums[j];if(seen.contains(twochar)){result.add(Arrays.asList(nums[i],nums[j],twochar));}seen.add(nums[j]); // 加入到哈希表,供后续查找}}return new ArrayList<>(result);}
}
方法二:双指针,时间复杂度
排序一次 O(n log n)
双指针部分是 O(n²),但跳过重复元素大幅减少不必要的操作
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums); // 排序先for (int i = 0; i < nums.length - 2; i++) {// 跳过重复的 nums[i]if (i > 0 && nums[i] == nums[i - 1]) continue;int left = i + 1;int right = nums.length - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum == 0) {res.add(Arrays.asList(nums[i], nums[left], nums[right]));// 跳过重复的 leftwhile (left < right && nums[left] == nums[left + 1]) left++;// 跳过重复的 rightwhile (left < right && nums[right] == nums[right - 1]) right--;left++;right--;} else if (sum < 0) {left++; // 增加和} else {right--; // 减小和}}}return res;}
}
方法三:
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result=new ArrayList<>();Arrays.sort(nums);//数组按升序排序Set<List<Integer>> set = new HashSet<>();for(int i=0;i<nums.length-2;i++)//取倒数第三个数{//跳过重复的nums[i]if(i>0&&nums[i]==nums[i-1])continue;int left=i+1;//相对顺序 nums[i]、nums[left]、nums[right]int right=nums.length-1;while(left<right){ int sum=nums[i]+nums[left]+nums[right];if(sum==0){//result.add(Arrays.asList(nums[i],nums[right],nums[left]));List<Integer> triplet=Arrays.asList(nums[i],nums[right],nums[left]);set.add(triplet);// 跳过重复的 left// while(left<right&&nums[left]==nums[left+1])// {left++;}// // 跳过重复的 right// while(left<right&&nums[right]==nums[right-1])// {right--;}left++;right--;}else if(sum<0){left++;}else{right--;// 和太大,right左移}}}// return result;return new ArrayList<>(set);}
}