题解 | #四数之和 三数之和类似 排序 + 双指针#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型ArrayList 
     * @param target int整型 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> fournumber (ArrayList<Integer> nums, int target) {
        if (nums.size() < 4){
            return new ArrayList<>();
        }
        Collections.sort(nums);
        HashSet<ArrayList<Integer>> ans = new HashSet<>();
        for (int i = 0; i < nums.size() - 3; i++) {
            //剪枝
            if (i >= 1 && nums.get(i) == nums.get(i - 1)){
                continue;
            }
            if (nums.get(i) + nums.get(i + 1) + nums.get(i + 2) + nums.get(i + 3) > target){
                break;
            }
            if (nums.get(i) + nums.get(nums.size() - 1) + nums.get(nums.size() - 2) + nums.get(nums.size() - 3) < target){
                continue;
            }
            for (int j = i + 1; j < nums.size() - 2; j++) {
                if (j >= i + 2 && nums.get(j) == nums.get(j - 1)){
                    continue;
                }
                if (nums.get(i) + nums.get(j) + nums.get(j + 1) + nums.get(j + 2) > target){
                    break;
                }
                if (nums.get(i) + nums.get(j) + nums.get(nums.size() - 2) + nums.get(nums.size() - 1) < target){
                    continue;
                }
                int left = j + 1;
                int right = nums.size() - 1;
                while (left < right){
                    while (left < right && nums.get(i) + nums.get(j) + nums.get(left) + nums.get(right) == target){
                        ArrayList<Integer> tmp = new ArrayList<>();
                        tmp.add(nums.get(i));
                        tmp.add(nums.get(j));
                        tmp.add(nums.get(left));
                        tmp.add(nums.get(right));
                        ans.add(tmp);
                        left++;
                        right--;
                    }
                    while (left < right && nums.get(i) + nums.get(j) + nums.get(left) + nums.get(right) > target){
                        right--;
                    }
                    while (left < right && nums.get(i) + nums.get(j) + nums.get(left) + nums.get(right) < target){
                        left++;
                    }
                }
            }
        }
        return new ArrayList<>(ans);
    }
}