相似题目 4sum

2sum

1. 3Sum My Submissions QuestionEditorial Solution

   Total Accepted: 115154 Total Submissions: 612489 Difficulty: Medium
   Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
   Note:
   Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
   The solution set must not contain duplicate triplets.
   For example, given array S = {-1 0 1 2 -1 -4},

   A solution set is:

   (-1, 0, 1)
   (-1, -1, 2)

分析：

311 / 311 test cases passed.

Status: Accepted

Runtime: 76 ms

beats 10.13%

突然发现，一个程序的思路很重要，反映在runtime上，以后贴上runtime来

衡量程序优劣，虽然只是一个小程序，但真正在大数据量的情况相差是很大的

之前用map存好任意两个数的和，慢很多，在以下的一个case中发现

改进后的只要1ms，而用map的需要50ms左右，以下是代码

思路：先固定一个数，其余两个数从两端夹逼，再这个过程自动去重

同时过滤排序中已经判定过的情况

时间复杂度：O(n2)

空间复杂度：O(1)

改进：

class Solution {public:    vector
     
      
       > threeSum(vector
       
        & nums) {        vector
        
         
           > res;        if(nums.size()<3)return res;        sort(nums.begin(),nums.end());        int n = nums.size();        for(int i=0;i
          

tmp; int sum2 = nums[beg]+nums[end]; if(sum2==-nums[i]){ tmp.push_back(nums[i]); tmp.push_back(nums[beg]); tmp.push_back(nums[end]); res.push_back(tmp); while(++beg

beg&&nums[end]==nums[end+1]); } else{ if(sum2<-nums[i])++beg; else --end; } } } return res; }};

用map的：

class Solution {public:    vector
     
      
       > threeSum(vector
       
        & nums) {        vector
        
         
           > res;        map
          
           
            ,int> mres; if(nums.size()<3)return res; map
            
             
              
                > > Two_map; for(int i=0;i
               
                (i,j)); } for(int i=0;i