请选择 进入手机版 | 继续访问电脑版
设为首页收藏本站

猿媛之家

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
热搜: 活动 交友 discuz
查看: 5775|回复: 0

3sum问题求解

[复制链接]

44

主题

48

帖子

198

积分

注册会员

Rank: 2

积分
198
发表于 2015-12-8 18:06:35 | 显示全部楼层 |阅读模式
   给定一个有n个元素的数组arr,是否存在三个数abc使得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[j] + arr[k] ==0)
                                {
                                                ArrayList<Integer>solution = new ArrayList<Integer>();
                                                solution.add(arr);
                                                solution.add(arr[j]);
                                                solution.add(arr[k]);
                                                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();
                }
    }
}
   显然这个算法的时间复杂度为On^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[i - 1]) {         
                                int begin = i + 1;
                                int end = arr.length - 1;                       
                                while (begin < end)
                                {
                                        //找到满足条件的数值对
                                        if (arr[begin] + arr[end] ==  -arr)
                                        {
                                                ArrayList<Integer> solution = new ArrayList<Integer>();
                                                solution.add(arr);
                                                solution.add(arr[begin]);
                                                solution.add(arr[end]);         
                                                result.add(solution);
                                                begin++;
                                                end--;
                                                //跳过重复的值,避免结果有重复
                                                while (begin < end && arr[end] == arr[end + 1])
                                                        end--;         
                                                while (begin < end && arr[begin] == arr[begin - 1])
                                                        begin++;                                       
                                        }
                                        else if (arr[begin] + arr[end] <  -arr)
                                        {
                                                begin++;                //在区间[begin+1,end]中继续查找
                                                //与arr[begin]相等的值一定不满足条件没有遍历的必要
                                                while (begin < end && arr[begin] == arr[begin - 1])
                                                        begin++;
                                        }
                                        else
                                        {
                                                end--; //在区间[begin,end-1]中继续查找
                                                while (begin < end && arr[end] == arr[end + 1])
                                                        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();
            }
    }
}


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|猿媛之家    

GMT+8, 2021-10-25 09:33 , Processed in 0.208624 second(s), 27 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表