Leet Code Medium 15 3Sum

2024-06-15 08:58

文章标签 15 code leet medium 3sum

本文主要是介绍Leet Code Medium 15 3Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目】

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)

【解析】

K Sum问题是一个系列，博客 http://tech-wonderland.net/blog/summary-of-ksum-problems.html 总结得比较完整，有兴趣可以去看。

作为初学者，我们用最简洁的思路来说一下这道题怎么解。

暴力解决法是每个人都能想到的，三层for循环，时间复杂度是O(n^3)，而且还要处理重复的问题，显然不是题目想要的解法。

那能不能降到O(n^2)？排序算法的时间复杂度为O(nlgn)，小于O(n^2)，那么我们不妨先对数组排个序。

排序之后，我们就可以对数组用两个指针分别从前后两端向中间扫描了，如果是 2Sum，我们找到两个指针之和为target就OK了，那 3Sum 类似，我们可以先固定一个数，然后找另外两个数之和为第一个数的相反数就可以了。

代码不难，先看了再说。

【Java代码】O(n^2)

[java]  view plain copy  
 public class Solution {  
     List<List<Integer>> ret = new ArrayList<List<Integer>>();  
       
     public List<List<Integer>> threeSum(int[] num) {  
         if (num == null || num.length < 3) return ret;  
           
         Arrays.sort(num);  
           
         int len = num.length;  
         for (int i = 0; i < len-2; i++) {  
             if (i > 0 && num[i] == num[i-1]) continue;  
             find(num, i+1, len-1, num[i]); //寻找两个数与num[i]的和为0  
         }  
           
         return ret;  
     }  
       
     public void find(int[] num, int begin, int end, int target) {  
         int l = begin, r = end;  
         while (l < r) {  
             if (num[l] + num[r] + target == 0) {  
                 List<Integer> ans = new ArrayList<Integer>();  
                 ans.add(target);  
                 ans.add(num[l]);  
                 ans.add(num[r]);  
                 ret.add(ans); //放入结果集中  
                 while (l < r && num[l] == num[l+1]) l++;  
                 while (l < r && num[r] == num[r-1]) r--;  
                 l++;  
                 r--;  
             } else if (num[l] + num[r] + target < 0) {  
                 l++;  
             } else {  
                 r--;  
             }  
         }  
     }  
 }  