wait 发表于 2015-12-8 18:06:35

3sum问题求解

   给定一个有n个元素的数组arr,是否存在三个数a,b,c使得a+b+c=0?找出所有的组合(不能有重复)。 方法一:蛮力法      最简单的方法就是对数组进行三重遍历,对于遍历到的三个数,判断是否满足题目要求,如果要求则输出,示例代码如下:import java.util.ArrayList; import java.util.ArrayList; public class Test {    public staticArrayList<ArrayList<Integer>> getThreeSum(int[] arr)     {       ArrayList<ArrayList<Integer>> result = newArrayList<ArrayList<Integer>>();            for(int i=0; i<arr.length;i++)      {            for(int j=i+1;j<arr.length; j++)            {                for(intk=j+1; k<arr.length; k++)                {                              if(arr + arr + arr ==0)                              {                                                ArrayList<Integer>solution = new ArrayList<Integer>();                                                solution.add(arr);                                                solution.add(arr);                                                solution.add(arr);                                                result.add(solution);                  }                }            }      }      return result;    }        public static voidmain(String[] args)    {                int arr[] = {-1, 0, 1, 2, -1 ,-4};                ArrayList<ArrayList<Integer>>result=getThreeSum(arr);                for(int i=0;i<result.size();i++)                {                              for(int j=0;j<result.get(i).size();j++)                              {                                                System.out.print(result.get(i).get(j)+"");                              }                              System.out.println();                }    }}   显然这个算法的时间复杂度为O(n^3),而且这种方法获取到的结果有重复
   方法二:排序法把数组排序,通过避免遍历重复的数字的方法可以解决结果重复的问题。实现代码如下:import java.util.ArrayList;import java.util.Arrays;
public class Test {        public static ArrayList<ArrayList<Integer>> getThreeSum(int[] arr)        {                ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();                if (arr==null || arr.length < 3)                        return result;                 Arrays.sort(arr);                 for (int i = 0; i < arr.length - 2; i++) {                        //避免重复的情况                        if (i == 0 || arr != arr) {                                       int begin = i + 1;                                int end = arr.length - 1;                                                        while (begin < end)                                {                                        //找到满足条件的数值对                                        if (arr + arr ==-arr)                                         {                                                ArrayList<Integer> solution = new ArrayList<Integer>();                                                solution.add(arr);                                                solution.add(arr);                                                solution.add(arr);                                                       result.add(solution);                                                begin++;                                                end--;                                                //跳过重复的值,避免结果有重复                                                while (begin < end && arr == arr)                                                        end--;                                                       while (begin < end && arr == arr)                                                        begin++;                                                                                }                                         else if (arr + arr <-arr)                                         {                                                begin++;                //在区间中继续查找                                                //与arr相等的值一定不满足条件没有遍历的必要                                                while (begin < end && arr == arr)                                                        begin++;                                        }                                         else                                        {                                                end--; //在区间中继续查找                                                while (begin < end && arr == arr)                                                        end--;                                                }                                }                               }                }                       return result;        }        public static void main(String[] args)    {            int arr[] = {-1, 0, 1, 2, -1 ,-4};            ArrayList<ArrayList<Integer>> result=getThreeSum(arr);            for(int i=0;i<result.size();i++)            {                    for(int j=0;j<result.get(i).size();j++)                    {                            System.out.print(result.get(i).get(j)+" ");                    }                    System.out.println();            }    }}

页: [1]
查看完整版本: 3sum问题求解