// @Title: 四数之和 (4Sum)
// @Author: qisiii
// @Date: 2024-04-12 23:12:56
// @Runtime: 25 ms
// @Memory: 44.6 MB
// @comment: 
// @flag: 
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length - 3; i++) {
            if(i!=0&&nums[i]==nums[i-1]){
                continue;
            }
            HashSet<Integer> jset=new HashSet<>();
            for (int j = i + 1; j < nums.length; j++) {
                if(jset.contains(nums[j])){
                    continue;
                }else{
                    jset.add(nums[j]);
                }
                List<List<Integer>> temp = twoSum(Arrays.copyOfRange(nums,j + 1, nums.length),(long) target - nums[i] - nums[j]);
                if (temp.size() > 0) {
                    for (List<Integer> list : temp) {
                        list.add(nums[i]);
                        list.add(nums[j]);
                        result.add(list);
                    }
                }
            }
        }
        return result;
    }

    public List<List<Integer>> twoSum(int[] nums, long target) {
        List<List<Integer>> result = new ArrayList<>();
        int left = 0, right = nums.length - 1;
        while (left < right) {
            if (nums[left] + nums[right] > target) {
                right--;
            } else if (nums[left] + nums[right] < target) {
                left++;
            } else {
                result.add(new ArrayList<>(Arrays.asList(nums[left], nums[right])));
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right + 1]) {
                    right--;
                }
            }
        }
        return result;
    }
}