企业官网建设流程全解析

题目：

给你一个整数数组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) { } }

分析：

（1）题目分析

三元组的定义：三个下标不同且满足数值之和相加等于0。需要返回的是由三个数组值组成的数组列表，不需要返回下标。

（2）提供代码分析

输入：整数数组

返回值：由整数列表组成的列表

（3）思路分析

可以对首先对随机数组进行排序，然后遍历下标 i 从0开始的所有元素：两层循环。

外层循环：

以 i 为起始点，每次循环使left = i + 1作为左指针，right = 数组长度 - 1当作右指针。

去重判断：

• 如果 nums[i] > 0 说明右边的值全部大于0，直接结束循环，无三元组。
• 如果 nums[i] == nums[i - 1] 证明相同值已经判断过，重复三元组，结束本次循环。

内层循环：

终止条件：左指针与右指针相遇

循环内容：判断 i ，right， left三个下标对应的数值之和 sum 的情况：

• 当 sum == 0 时，满足三元组条件，进行存储，然后判断nums[right--]，nums[left++]的情况去除重复值。
• 如果sum < 0 说明当前的left值过小，left++。
• 如果sum > 0 说明当前的right值过大，right--。

完整代码：

class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); // 对数组内容进行排序 Arrays.sort(nums); int n = nums.length; for(int i = 0; i < n; i++){ // 如果第一个数已经大于0，后面全部更大，直接break结束循环 if(nums[i] > 0)break; // 对i去重，跳过重复数字 if(i > 0 && nums[i] == nums[i - 1])continue; int left = i + 1; int right = n - 1; while(left < right){ int sum = nums[i] + nums[left] + nums[right]; // 找到一组解 if(sum == 0){ // asList方法将数组以列表的形式返回 res.add(Arrays.asList(nums[i], nums[left], nums[right])); // 对left去重 while(left < right && nums[left] == nums[left + 1])left++; // 对right去重 while(left < right && nums[right] == nums[right - 1])right--; left++; right--; // 如果sum < 0 说明当前的left值过小 }else if(sum < 0){ left++; // 如果sum > 0 说明当前的right值过大 }else{ right--; } } } return res; } }

复杂度分析：

• 时间复杂度：O(nlogn) + O(n²) ~O(n²)
• 空间复杂度：O(logn)（不包含输出结果）