15.三数之和

题目描述：

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：

答案中不可以包含重复的三元组。

示例

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

解答：

public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> rs=new ArrayList<List<Integer>>();
        //边界条件
        if (nums==null||nums.length<3) {
            return rs;
        }
        //将数组排序
        Arrays.sort(nums);
        //hashset 存储唯一值
        HashSet<ArrayList<Integer>> hSet=new HashSet<ArrayList<Integer>>();
        //排序后确定一个值
        for (int i = 0; i < nums.length-2; i++) {
            //确定一个值后，左右两侧向中间靠拢
            int low=i+1;
            int high=nums.length-1;
            while(low<high){
                int sum=nums[i]+nums[low]+nums[high];
                if (sum==0) {
                    //直接定义list初始化
                    ArrayList<Integer> tuple=new ArrayList(Arrays.asList(nums[i],nums[low],nums[high]));
                    //不重复
                    if (!hSet.contains(tuple)) {
                        hSet.add(tuple);
                        //结果中才添加
                        rs.add(tuple);
                    }
                    //继续靠拢
                    low++;
                    high--;
                }else if (sum<0) {
                    //和太小 往右移动
                    low++;
                }else {
                    //和太大，往左移
                    high--;
                }
            }
        }
        /*
         暴力，超时间
        for (int i = 0; i < nums.length-2; i++) {
            for (int j = i+1; j < nums.length-1; j++) {
                for (int k = j+1; k < nums.length; k++) {
                    if (nums[i]+nums[j]+nums[k]==0) {
                        //System.out.println(nums[i]+";"+nums[j]+";"+nums[k]);
                        List<Integer> tuple=new ArrayList(Arrays.asList(nums[i],nums[j],nums[k]));
                        Collections.sort(tuple);
                        if (!rs.contains(tuple)) {
                            rs.add(tuple);
                        }
                    }
                }
            }
        }*/
        for (int i = 0; i < rs.size(); i++) {
            for (int j = 0; j < rs.get(i).size(); j++) {
                System.out.print(rs.get(i).get(j)+";");
            }
            System.out.println();
        }
        return rs;
    }

注意：

1.化繁为简，简化成两个数相加，找目标和的函数
2.注意要先把数组排序，固定一个值，然后low和high分别从i+1和length-1往中间走
3.为了防止重复添加，可以使用HashSet来避免重复
4.判空条件是看num小于3