数组元素求指定和

要求

给出一个无序数组，求出该数组中相加为0的三个元素的集合，结果不可重复

例. 给出数组{-1,0,1,2,-1,4}，相加得0的三个元素的集合为[[-1, -1, 2], [-1, 0, 1]]

实现

/**
 * 数组元素求指定和
 * */
public class demo {
    public static void main(String[] args) {
        //测试数据
        int[] nums = {-1,0,1,2,-1,4};
        //输出结果
        System.out.println(threeSum(nums));

    }

    public static List<List<Integer>> threeSum(int[] nums){
        //排序
        Arrays.sort(nums);
        //创建结果集
        ArrayList<List<Integer>> lists = new ArrayList<>();
        //调用辅助方法
        long start = System.currentTimeMillis();
        helper(lists,nums,0,new ArrayList<Integer>(),0);
        long end = System.currentTimeMillis();

        System.out.println(end-start);


        return lists;
    }

    /**
     * @param lists 结果集
     * @param source 原数组
     * @param target 目标和
     * @param list 结果集中的项（和为0的元素集合）
     * @param index 起始索引
     * */
    private static void helper(ArrayList<List<Integer>> lists, int[] source, int target, ArrayList<Integer> list, int index) {
        //开始遍历
        for (int i = index; i < source.length; i++) {
            //判断元素和小于目标和，因为要求是加法，所以使用减法起来判断还需要多大的数才能满足目标和
            if (source[i] <= target) {
                //在集合中添加元素
                list.add(source[i]);
                //递归 目标和减去当前元素值作为新的目标和
                helper(lists, source, target - source[i], list, i + 1);
                //依次删除末端元素，保证取到所有结果，
                //因为可能出现多个数相加得0，但这多个数中又有数相加得0的情况
                list.remove(list.size() - 1);
            }
        }

        //如果此时目标和为0
        if( target == 0){
            //且不出现重复的集合
            if(!lists.contains(list)){
                //将集合放入结果集
                lists.add(new ArrayList<>(list));
            }
        }

        //删除长度大于3的集合
        //使用迭代器避免出现remove方法异常
        Iterator<List<Integer>> iterator = lists.iterator();
        while (iterator.hasNext()){
            if (iterator.next().size() != 3){
                iterator.remove();
            }
        }

    }
}