package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LC_18 {
    public static void main(String[] args) {
        System.out.println(fourSum(new int[]{1000000000, 1000000000, 1000000000, 1000000000}, -294967296));
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 4) return res;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            long tar;
            tar = target - nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                int l = j + 1;
                int r = nums.length - 1;
                while (l < r) {
                    if (nums[j] + nums[l] == tar - nums[r]) {
                        ArrayList<Integer> res_tmp = new ArrayList<>();
                        Collections.addAll(res_tmp, nums[i], nums[j], nums[l], nums[r]);
                        res.add(res_tmp);
                        while (l + 1 < r && nums[l] == nums[l + 1]) l++;
                        while (l < r - 1 && nums[r] == nums[r - 1]) r--;
                        l++;
                        r--;
                    } else if (nums[j] + nums[l] > tar - nums[r]) r--;
                    else if (nums[j] + nums[l] < tar - nums[r]) l++;
                }
                while (j + 1 < nums.length && nums[j] == nums[j + 1]) j++;
            }
        }
        return res;
    }
}