企业官网建设流程全解析

题目：三数之和

描述：给你一个整数数组nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为0且不重复的三元组。注意：答案中不可以包含重复的三元组。

示例：

输入：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] 。 注意，输出的顺序和三元组的顺序并不重要。

算法思路：

由于起始数组是无序的导致浪费时间，这里先进行从小到大排序，然后直接遍历数组拿第一个值 a ，然后退化为两数之和，用双指针指向这两个数 b ，c ，当 a + b + c > 0 时，b 已经是当前最少的值了，移动右指针 c 使总和变小，当总和小于 0 时，同理移动左指针 b，相等时候存入三个值，中间可以跳过一些数组内相同的值进行优化。

class ThreeSum{ public List<List<Integer>> threeSum(int[] nums) { List result = new ArrayList(); Arrays.sort(nums); for (int i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]){ continue; } if (nums[i] + nums[i+1] + nums[i+2] > 0){ break; } if (nums[i] + nums[nums.length - 1] + nums[nums.length - 2] < 0){ continue; } int k = i + 1; int j = nums.length - 1; while(k < j){ if (nums[i] + nums[k] + nums[j] < 0){ k++; }else if (nums[i] + nums[k] + nums[j] > 0){ j--; }else { List list = new ArrayList(); list.add(nums[i]); list.add(nums[k]); list.add(nums[j]); result.add(list); k++; while(k < j && nums[k] == nums[k - 1]){ k++; } j--; while(k < j && nums[j] == nums[j + 1]){ j--; } } } } return result; } }

注：只为记录自己的练习过程，方便回顾！