leetcode:3Sum (三个数的和)

Question: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.

Node:

  • 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)

给定一个数组S,里边有n个整数,数组中有没有三个数a、b、c使他们相加等于0,找出数组中唯一的三个数,注意a<=b<=c,答案不能包括相同的一组数。

比如,这个数组是{-1 0 1 2-1 -4}答案是(-1,0,1)(-1,-1,2),不能有相同的.

算法思路:① 这个题使用的比较笨的方法,时间复杂度都能达到O(n^3),很好理解,就是使用蛮力算法穷举每一种可能,设置了三个循环,本来对这个通过不抱希望,但是leetcode竟然通过了。

     ② getArray(int num1,int num2,int num3)是对num1、num2、num3排序的。

     ③ boolean compareArray(ArrayList<ArrayList<Integer>> array1,ArrayList<Integer> array2)是判断array1中是否有和array2相同的小组数的。

代码设计:

 1 class Solution15 {
 2     public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
 3         // Note: The Solution object is instantiated only once and is reused by each test case.
 4         ArrayList <ArrayList<Integer>> arrayList=new ArrayList<ArrayList<Integer>>();//最终返回的容器类型
 5        // Integer dist[][]=new Integer[num.length][num.length];
 6         for(int i=0;i<num.length;i++){//三重循环时间复杂度太高, 可是也没想起其他好办法
 7             for(int j=i+1;j<num.length;j++){
 8                 for(int k=j+1;k<num.length;k++){
 9                     if(num[i]+num[j]+num[k]==0){
10                         ArrayList<Integer> temp=getArray(num[i],num[j],num[k]);
11                         if(!compareArray(arrayList, temp))
12                             arrayList.add(temp);
13                     }
14                 }
15             }
16         }
17         return arrayList;
18     }
19     boolean compareArray(ArrayList<ArrayList<Integer>> array1,ArrayList<Integer> array2){
20         for(int i=0;i<array1.size();i++){//这个函数的作用是判断array1中是否已经包含有array2
21             if(array1.get(i).get(0)==array2.get(0)&&array1.get(i).get(1)==array2.get(1))
22                 return true;
23         }
24         return false;
25     }
26     ArrayList<Integer> getArray(int num1,int num2,int num3){
27         ArrayList<Integer> arrayList=new ArrayList<Integer>();
28         if(num1>num2){
29             num1=num1+num2;//这一部分作用是交换两个数
30             num2=num1-num2;
31             num1=num1-num2;
32         }
33         if(num3<num2){
34             num3=num3+num2;
35             num2=num3-num2;
36             num3=num3-num2;
37         }
38         if(num1>num2){
39             num1=num1+num2;
40             num2=num1-num2;
41             num1=num1-num2;
42         }
43         arrayList.add(num1);//这个时候num1 num2 num3 按从小到大的顺序排列
44         arrayList.add(num2);
45         arrayList.add(num3);
46         return arrayList;
47     }
48 }

写的算法比较麻烦,欢迎各位留言交流。2013-10-19

原文地址:https://www.cnblogs.com/zhaolizhen/p/3Sum.html