哈密市网站建设_网站建设公司_UI设计_seo优化

一、思路：

1.为方便双指针以及跳过相同元素，先把nums排序。

2.枚举nums[i]，将问题转化成nums[j] + nums[k] = -nums[i]，转变成两数之和的问题。

3.题目要求答案中不能有重复的三元组，因此要避免重复。

（1）在外层循环中，如果发现nums[i] = nums[i - 1]，那么nums[i]与后面两个数组成的和为0的三元组，nums[i - 1]也能组成一模一样的三元组，这就重复了。所以遇到nums[i] = nums[i - 1]的情况，直接continue。

（2）在内层循环中，当三数之和等于0时，为避免把相同的三元组计入答案，跳过后续相同的nums[j]和nums[k]（也可以只跳过相同的nums[j]）。

二、优化：

1.优化一：如果nums[i]与后面最小的两个数相加nums[i] + nums[i + 1] + nums[i + 2] > 0，那么后面不可能存在三数之和等于0，break外层循环（终止循环，执行循环后面的代码）。

2.优化二：如果nums[i]与后面最大的两个数相加nums[i] + nums[n - 2] + nums[n - 1] < 0，那么内层循环不可能存在三数之和等于0，但继续枚举，nums[i]可以变大，所以后面还有机会找到三数之和等于0，continue外层循环（跳过本次迭代，进入下一次循环迭代）。

三、复杂度分析：

1.时间复杂度：O(n^2)，其中n为nums的长度。排序O(logn)，外层循环枚举第一个数，做法是O(n)双指针，所以总的时间复杂度为O(n^2)。

2.空间复杂度：O(1)。

附代码：

class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); int n = nums.length; for(int i = 0;i < n - 2;i++){ int x = nums[i]; if(i > 0 && x == nums[i - 1]){ //跳过重复数字 continue; } if(x + nums[i + 1] + nums[i + 2] > 0){ //优化1 break; } if(x + nums[n - 2] + nums[n - 1] < 0){ //优化2 continue; } int j = i + 1; int k = n - 1; while(j < k){ int sum = x + nums[j] + nums[k]; if(sum > 0){ k--; }else if(sum < 0){ j++; }else{ //三数之和为0 res.add(List.of(x,nums[j],nums[k])); //数组已经排序，相同的数字会相邻，需跳过重复数字 j++; k--; //跳过重复数字 while(j < k && nums[j] == nums[j - 1]){ j++; } //跳过重复数字 while(k > j && nums[k] == nums[k + 1]){ k--; } } } } return res; } }