3 Sum问题

不念不忘少年蓝@ 2022-09-25 00:28 239阅读 0赞

3 Sum 问题

题目链接：lintcode 3 sum (http://www.lintcode.com/en/problem/3sum/)

基本思路

一会写

代码块

具体实现如下：

  1. class Solution {
  2. public:    
  3.     /**
  4.      * @param numbers : Give an array numbers of n integer
  5.      * @return : Find all unique triplets in the array which gives the sum of zero.
  6.      */
  7.     vector<vector<int> > threeSum(vector<int> &nums) 
  8.     {
  9.         // write your code here
  10.         int i,j,l,r;
  11.         vector<vector<int>> res;
  12.         map<int,int> hash;
  13.         if(nums.size()<3)
  14.             return res;
  15.         sort(nums.begin(),nums.end());
  16.         for(i=0;i<nums.size()-1;i++)
  17.         {
  18.             if(i>0 && nums[i]==nums[i-1])
  19.                 continue;
  20.             l=i+1;
  21.             r=nums.size()-1;
  22.             while(l<r)
  23.             {
  24.                 int ans=nums[i]+nums[l]+nums[r];
  25.                 if(ans==0)
  26.                 {
  27.                     res.push_back({nums[i],nums[l],nums[r]});
  28.                     l++;
  29.                     r--;
  30.                     while(l<r && nums[l]==nums[l-1])
  31.                         l++;
  33.                     while(r>l && nums[r]==nums[r+1])
  34.                         r--;
  35.                 }else if(ans>0)
  36.                     r--;
  37.                 else 
  38.                     l++;
  39.             }
  40.         }
  41.         return res;
  42.     }
  43. };

发表评论

表情：
评论列表 （有 0 条评论，239人围观）

还没有评论，来说两句吧...

相关阅读

    相关 2sum问题和3sum问题

    算法 这个书，190页介绍了 这两个问题 。 2sum的意思是 在一组数中，找到 两个数的和为零。有多少个这样的组合。 3sum是 找 有多少三个数的组合 ，他们的和为零

    ╰+攻爆jí腚メ╰+攻爆jí腚メ/ 0 赞/ 291 阅读

    相关 3Sum

    [原题链接][Link 1] 给一个拥有n个元素的数组S，S中是否会有a，b，c三个元素使得a+b+c=0?寻找出满足该条件的所有唯一三元组。 Note： 答案中必须不

    水深无声水深无声/ 0 赞/ 263 阅读