题目

解答

 public static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);

        ArrayList<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }

        HashSet<List<Integer>> result = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {

            if (target >= 0 && nums[i] > target) {
                break;
            }

            ArrayList<Integer> clone = (ArrayList<Integer>) list.clone();
            clone.remove(i);

            int newTarget = target - nums[i];
            //找到三个数字之和等于target-nums[i]

            for (int j = i+1; j < nums.length; j++) {

                if (newTarget >= 0 && nums[j] > newTarget) {
                    break;
                }

                int one = j + 1;
                int two = nums.length - 1;

                while (one < two) {
                    if (nums[one] + nums[two] + nums[j] == newTarget) {
                        List<Integer> asList = Arrays.asList(nums[i], nums[one], nums[two], nums[j]);
                        asList.sort(Integer::compare);
                        result.add(asList);
                        one++;
                        two--;
                    } else if (nums[one] + nums[two] + nums[j] < newTarget) {
                        one++;
                    } else {
                        two--;
                    }
                }
            }
        }

        return new ArrayList<>(result);
    }

## 三数之和外面套一层循环