15. 三数之和：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。 注意：答案

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]

提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105

思路

使用双指针+数组排序解决问题：

1. 将数组排序，第一个指针指向最左边（最小值），第二个指向最右边（最大值）
2. 因为数组是从小到大，所以前面的肯定要有是负数的，才能保证所求的三个数相加等于0，因此将第一个数取反，当第一个指针和第二个指针相加等于第一个数的相反数时，便可以证明这三个数相加等于0
3. 第一个指针是在第一个数的后面，第二层for循环退出标志是第二个和第三个指针重合（相等）
4. 存在的三个数可以这样理解：第一个数是目标值（要求第二个数和第三个数相加要等于其相反数）；第二个数类似有双指针的左指针；第三个数类似于双指针的右指针；
5. 第二个数的下标要大于第一个数的下标，要小于第三数的下标

代码

class Solution {public List<List<Integer>> threeSum(int[] nums) {//获取数组长度int n = nums.length;//对数组进行排序，方便后面的相加操作Arrays.sort(nums);//使用list集合保存所有等于0的情况下的三元数组List<List<Integer>> ans = new ArrayList<List<Integer>>();//获取第一个元素的循环，最左边的数的下标for(int first=0;first<n;first++){//如果第一个元素大于0，后面的元素都会比它大，肯定是不成立的if(nums[first]>0) break;//如果当前情况下，该元素重复，那么continue进入下一次循环if(first>0 && nums[first] == nums[first-1]) continue;//获取最右边的数的下标int third = n-1;//获取当第一个数和第三个数相加后需要等于的值int target = -nums[first];//获取第二个数，循环//当第二个数和第三个数相加等于target时，便加入集合for(int second=first+1;second<n;second++){//如果当前情况下，该元素重复，那么continue进入下一次循环if(second>first+1 && nums[second]==nums[second-1]){continue;}//保证第二个数在第三个数的左边//且第二和三个数相加大于第一个数的相反数的话，第三个数需要向左移动一位while(second<third && nums[second]+nums[third]>target){--third;}//如果第二个和第三个数重合，便可以提前退出循环if(second==third) break;//如果第二个和第三个数相加等于第一个数的相反数的话，往集合中添加if (nums[second] + nums[third] == target) {List<Integer> list = new ArrayList<Integer>();list.add(nums[first]);list.add(nums[second]);list.add(nums[third]);ans.add(list);}}}return ans;}
}

代码说明

看注释。。。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！