No.015 3Sum

15. 3Sum

  • Total Accepted: 131800
  • Total Submissions: 675028
  • Difficulty: Medium

  Given an array S of n integers, are there elements abc in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

  Note: 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] ] 思路:   首先说点题外话,对于2Sum,3Sum,以及后面的4Sum,kSum等是一个系列的,具体的讨论在这篇文章中有提到,大家感兴趣的可以看看:http://www.sigmainfy.com/blog/summary-of-ksum-problems.html

  回到正文,这道题很容易想到的是暴力解法,这也是我们通常采用的办法,但是这样的方法的复杂度是O(n3),再加上去重的复杂度,这样的代码在leetcode是无法成功运行的。   对于简化的思路,我自己没有想出来,网上参考的是:【LeetCode】3Sum 解题报告

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

  1 public class No_015 {
  2     /*
  3      * 方法一:暴力解法
  4      */
  5     public List<List<Integer>> threeSum(int[] nums) {
  6         List<List<Integer>> res = new ArrayList<List<Integer>>() ;
  7         if(nums == null || nums.length < 3){
  8             return res ;
  9         }
 10         List<Integer> list = null ;
 11         for(int i = 0 ; i < nums.length-2 ; i++){
 12             for(int j = i+1 ; j < nums.length-1 ; j++){
 13                 for(int k = j+1 ; k < nums.length ; k++){
 14                     if((nums[i] + nums[j] + nums[k]) == 0){
 15                         list = toRange(nums,i,j,k) ;
 16                         if(!isContain(res,list)){
 17                             res.add(list) ;
 18                         }  
 19                     }
 20                 }
 21             }
 22         }
 23         return res ; 
 24     }    
 25     
 26     /*
 27      * 对三个数之和为0的数加入list的时候进行排序,方便后面去重
 28      * 
 29      * 唉,怎么没想到一开始就对曾格格数组进行排序呢???
 30      */
 31     private List<Integer> toRange(int [] nums ,int i , int j , int k){
 32         List<Integer> list = new ArrayList<Integer>() ;
 33         int max = nums[i]>nums[j]?nums[i]:nums[j] ;
 34         int min = nums[i]+nums[j]-max ;
 35         max = max>nums[k]?max:nums[k] ;
 36         min = min<nums[k]?min:nums[k] ;
 37         list.add(min) ;
 38         list.add(nums[i]+nums[j]+nums[k]-max-min) ;
 39         list.add(max) ;
 40         return list ;
 41     }
 42     /*
 43      * 检查是否有重复
 44      */
 45     private boolean isContain(List<List<Integer>> res , List<Integer> list){
 46         if(res == null || res.size() == 0){
 47             return false ;
 48         }
 49         for(List<Integer> each:res){
 50             if(each.get(0) == list.get(0) && each.get(1) == list.get(1)){
 51                 return true ;
 52             }
 53         }
 54         return false ;
 55     }
 56     
 57     /*
 58      * 方法二:首先进行排序,然后根据排序之后的数组,从两边到中间的办法查询,这样复杂度为o(n^2)
 59      */
 60     List<List<Integer>> ret = new ArrayList<List<Integer>>();
 61     public List<List<Integer>> threeSum2(int[] num) {
 62 
 63         if (num == null || num.length < 3)
 64             return ret;
 65 
 66         Arrays.sort(num);
 67 
 68         int len = num.length;
 69         for (int i = 0; i < len - 2; i++) {
 70             if (i > 0 && num[i] == num[i - 1])
 71                 continue;
 72             find(num, i + 1, len - 1, num[i]); // 寻找两个数与num[i]的和为0
 73         }
 74 
 75         return ret;
 76     }
 77 
 78     public void find(int[] num, int begin, int end, int target) {
 79         int l = begin, r = end;
 80         while (l < r) {
 81             if (num[l] + num[r] + target == 0) {
 82                 List<Integer> ans = new ArrayList<Integer>();
 83                 ans.add(target);
 84                 ans.add(num[l]);
 85                 ans.add(num[r]);
 86                 ret.add(ans); // 放入结果集中
 87                 while (l < r && num[l] == num[l + 1])
 88                     l++;
 89                 while (l < r && num[r] == num[r - 1])
 90                     r--;
 91                 l++;
 92                 r--;
 93             } else if (num[l] + num[r] + target < 0) {
 94                 l++;
 95             } else {
 96                 r--;
 97             }
 98         }
 99     }  
100     
101 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏分布式系统和大数据处理

C#理解泛型(译)

Visual C# 2.0 的一个最受期待的(或许也是最让人畏惧)的一个特性就是对于泛型的支持。这篇文章将告诉你泛型用来解决什么样的问题,以及如何使用它们来提高...

813
来自专栏mukekeheart的iOS之旅

Java基础整理(1)

1、源代码的文件名必须与公共类(public)的类名一致,而且一个源代码文件中最多只能有一个公共类(public) ---- 2、注释: 3种 行注释  以双斜...

2517
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——IdentityHashMap

1633
来自专栏前端儿

表达式求值(1)

Dr.Kong设计的机器人卡多掌握了加减法运算以后,最近又学会了一些简单的函数求值,比如,它知道函数min(20,23)的值是20 ,add(10,98) 的值...

1792
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——IdentityHashMap

3809
来自专栏java初学

hashMap原理(java8)

37017
来自专栏杨熹的专栏

【LEETCODE】模拟面试-39. Combination Sum

和subset区别:规定了子集的sum==target 注意,这里传递的起始位置是i,而不是position+1,but why??? helper(res, ...

2845
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高十六】集合List接口详解

在编写java程序中,我们最常用的除了八种基本数据类型,String对象外还有一个集合类,在我们的的程序中到处充斥着集合类的身影!java中集合大家族的成员实在...

2533
来自专栏xingoo, 一个梦想做发明家的程序员

Java程序员的日常 —— 《编程思想》持有对象

集合框架可以说是Java里面必备的知识点了,日常的使用中也会遇到各种情况需要使用到集合。下面就简单介绍下各种集合的使用场景: ? List List可以看...

2188
来自专栏Coding迪斯尼

使用普拉特分析法解析极为复杂的算术表达式

1063

扫码关注云+社区

领取腾讯云代金券