算法之旅-Hot100—三数之和

题目三数之和描述给你一个整数数组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 ListListInteger 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[i1] nums[i2] 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; } }注只为记录自己的练习过程方便回顾