LeetCode OJ：Three Sum（三数之和）-白红宇

LeetCode OJ：Three Sum（三数之和）

阅读量：6158 次

发布时间：2019-06-21

本文共 2719 字，大约阅读时间需要 9 分钟。

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) 大体的思想先将数组排序，从小到大取vector中的数first，再从剩下的数中取和等于 0 - first 的数即可。下面是代码（一开始没想出来，然后参考了别人的解法在写出来，一般的三层循环谁都能想到，但是时间复杂度太高，这里的这个时间复杂度应该是O（N^2）,还是可以接受的）

1 class Solution { 2 public: 3     vector
     
      
       > threeSum(vector
       
        & nums)  4     { 5         vector
        
         
          > result; 6         int sz = nums.size(); 7         sort(nums.begin(), nums.end()); 8         for (int i = 0; i < sz - 2; ++i){ 9             twoSum(nums, i + 1, 0 - nums[i], result);10             while(nums[i] == nums[i + 1]) ++i;//这一步要注意，防止得出重复的vector11         }12         return result;13     }14     15     void twoSum(vector
          
            & nums, int start, int value, vector
           
            
             > & ret)16 {17 int beg = start;18 int end = nums.size()-1;19 while (beg < end){20 int sum = nums[beg] + nums[end];21 if (sum < value)22 beg++;23 else if (sum > value)24 end--;25 else{26 ret.push_back(vector
             
              {nums[start - 1], nums[beg], nums[end]});27 while (nums[beg + 1] == nums[beg]) beg++;//这一步的处理应该注意，防止出现相同的vector28 while (nums[end - 1] == nums[end]) end--;29 beg++, end--;30 }31 }32 }33 };

java版的代码如下所示：

(由于不太熟悉ArrayList和List之间的关系，写起来感觉各种坑爹啊，注意下List和ArrayList之间的各种转换就可以了，代码如下)：

1 public class Solution { 2     List
     
      
       > ret = new ArrayList
       
        
         >(); 3              4     public List
         
          
           > threeSum(int[] nums) { 5 Arrays.sort(nums); 6 for(int i = 0; i < nums.length - 2; ++i){ 7 twoSum(nums, i+1, 0 - nums[i]); 8 while(i < nums.length - 2 && nums[i] == nums[i+1]) 9 ++i;10 }11 return ret;12 }13 14 public void twoSum(int[] nums, int start, int value)15 {16 int beg = start;17 int end = nums.length - 1;18 while(beg < end){19 if(nums[beg] + nums[end] == value){20 List
           
             list = new ArrayList
            
             ();21 list.add(nums[start - 1]);22 list.add(nums[beg]);23 list.add(nums[end]);24 ret.add(list);25 while(beg < end && nums[beg+1] == nums[beg]) 26 beg++;27 while(beg < end && nums[end-1] == nums[end]) 28 end--;29 beg++;30 end--;31 32 }else if(nums[beg] + nums[end] > value){33 end--;34 }else{35 beg++;36 }37 }38 }39 }

PS:同样的4Sum问题也可以转换成上面的3Sum问题，从而递归的求解，KSum问题也是一样

转载于:https://www.cnblogs.com/-wang-cheng/p/4856282.html

你可能感兴趣的文章