【LeetCode】15.三数之和

题目

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

• 满足 i != j、i != k 且 j != k （下标不同）
  
• nums + nums[j] + nums[k] == 0
  
• 不重复的三元组
  

算法解法

算法一： 排序 + 暴力枚举 + set去重 （O(                                             n                            3                                       n^{3}                  n3)）

排序再枚举，可以将重复的三元组酿成雷同的三元组，再去重即可。

简单解法，不讲解。
算法二： 排序 + 双指针

一旦排序应该思考能否利用双指针或者二分。

• 排序
  
• 固定一个数a
  
• 在该数后面的区间内，利用双指针算法不停寻找两个数的和等于-a即可
  
• 双指针算法：由于排序了，所以如果两个数相加如果大于目的值，分析中间的数字已经不可能等于目的值了，只有减小最大值（right–），才有机会得到目的值。反之，如果两个数相加小于目的值，直接left++；
  
  
  
  

• 细节问题：
  
  
  
  • 去重
    
    
    
    • 由于排序，我们会获得雷同的结果，所以我们固定的数字如果与前一个雷同，必要跳过。（跳过重复元素）
      
    • 双指针算法之间，left和right指针也必要跳过重复元素，缘故原由是由于两个数字相加已经得到了-a，那么这两个数字必须一起存在才能得到对应的-a。也就是要么重复这两个数字，要么不能得到-a。
      
    
    
  
  

代码

1. class Solution {
2. public:
3.     vector<vector<int>> ret;
4.     vector<vector<int>> threeSum(vector<int>& nums) {
5.         //排序
6.         sort(nums.begin(),nums.end());
8.         int n = nums.size();
9.         for(int i =0;i<n;) //固定数a
10.         {
11.             //利用双指针解决问题
12.             int left = i+1;
13.             int right = n-1;
14.             int target = -nums[i];
16.             while(left < right)
17.             {
18.                 int sum = nums[left] + nums[right];
19.                 if(sum > target) right--;
20.                 else if(sum < target) left++;
21.                 else
22.                 {
23.                     ret.push_back({nums[i],nums[left],nums[right]});
24.                     left++,right--;
25.                     //去重并且防止越界
26.                     while(nums[left] == nums[left-1] && left < right)left++;
27.                     while(nums[right] == nums[right+1] && right > left)right--;
28.                 }
29.             }
30.             //去重固定元素
31.             i++;
32.             while(i<n && nums[i] == nums[i-1]) i++;
33.         }
34.         return ret;
35.     }
36. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。