三数之和（leetcode15）
给你一个包含 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]]分析：
不重复 的本质是什么？
我们保持三重循环的大框架不变，只需要保证： 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素； 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。 我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求。 同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复
这种方法的时间复杂度仍然为
这个方法就是我们常说的「双指针」，
当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 O(N^2)减少至 O(N)。
注意到我们的伪代码中还有第一重循环，时间复杂度为
代码如下：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
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;
}
}
下面两个是自己写的方式这里做下记录
//优化：双指针法
public static List<List<Integer>> threeSum1(Integer[] nums) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
Arrays.sort(nums);//排序
int len = nums.length;
//确保每一次循环中，和上一次枚举的数不同是为了不重复
for(int i=0;i<len-2;i++){//第一层循环
int first = nums[i];
if(i>0&&first==nums[i-1]){//在第一层循环，需要和上一次枚举的数不同
continue;
}
int k=len-1;
int target = -first;
for(int j=i+1;j<len-1;j++){//第二层循环
int second=nums[j];
if(j>i+1&&second==nums[j-1]){//在第二层循环，需要和上一次枚举的数不同
continue;
}
while(j<k&&second+nums[k]>target){
--k;
}
if(j==k) break;
if(second+nums[k]==target){
List<Integer> arr = new ArrayList<Integer>();
arr.add(first);
arr.add(second);
arr.add(nums[k]);
list.add(arr);
}
}
}
return list;
}
//三重循环
//ac过程中超出时间限制
public static List<List<Integer>> threeSum(Integer[] nums) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
Arrays.sort(nums);//排序
int len = nums.length;
//确保每一次循环中，和上一次枚举的数不同是为了不重复
for(int i=0;i<len-2;i++){//第一层循环
int first = nums[i];
if(i>0&&first==nums[i-1]){//在第一层循环，需要和上一次枚举的数不同
continue;
}
for(int j=i+1;j<len-1;j++){//第二层循环
int second=nums[j];
if(j>i+1&&second==nums[j-1]){//在第二层循环，需要和上一次枚举的数不同
continue;
}
for(int k=j+1;k<len;k++){//第三层循环
int third = nums[k];
if(k>j+1&&third==nums[k-1]){//在第三层循环，需要和上一次枚举的数不同
continue;
}
if(first+second+third==0){
List<Integer> arr = new ArrayList<Integer>();
arr.add(first);
arr.add(second);
arr.add(third);
list.add(arr);
}
}
}
}
return list;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-01-28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
