15. 三数之和 双指针经典题目
15. 三数之和
给你一个整数数组
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 。提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
双指针
1.5H
分为几步骤
1.定义结果集
2.排序
3.剪枝操作
4.去除重复的值
5.定义指针
6.让left从左到右 让right从右到左进行遍历
7.满足条件后纳入结果集 但是也要注意去重
public List<List<Integer>> threeSum(int[] nums) {//没让我们返回下标 所以可以排序//总体思路//1.排序 1.5.剪枝 2.去重i 3.定义指针 4.收获结果 5.去重List<List<Integer>> resultList = new ArrayList<>();Arrays.sort(nums);for(int i = 0; i < nums.length; i++){//剪枝if(nums[i] > 0){return resultList;}//去重iif(i>0 && nums[i]==nums[i-1]){continue;}//定义指针 i = a ; left = b ; right = cint left = i + 1;int right = nums.length - 1;//收获结果集 left -> <- rightwhile(right > left){//这里起码要收一个集合再去重,否则会一个都没有比如00000那个测试用例if(nums[i] + nums[left] + nums[right] == 0){//将数组转换为list添加到结果集 asList返回的是一个List 【常用操作】resultList.add(Arrays.asList(nums[i],nums[left],nums[right]));//去重 while(right > left && nums[left] == nums[left+1]){left++;}while(right > left && nums[right] == nums[right-1]){right--;}//更新指针left++; right--;//如果结果大于0则右边的数减少来试数}else if(nums[i] + nums[left] + nums[right] > 0){right--;//如果结果小于0则左边的数来增加来试数}else if(nums[i] + nums[left] + nums[right] < 0){left++;}} } return resultList;}