四数之和

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) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (nums.size() < 4) {
            return res;
        }
        Collections.sort(nums);
        int n = nums.size();
        for (int i = 0; i < n - 3; i++) {
            //对第一个数进行去重
            if (i > 0 && nums.get(i).equals(nums.get(i - 1))) {
                continue;
            }
            //直至四数之和大于target还没有找到结果，就停止遍历
            if ((long) nums.get(i) + nums.get(i + 1) + nums.get(i + 2) + nums.get(
                        i + 3) > target) {
                break;
            }
            //找到与最大的三个数的四数之和大于target的，根据这个区间寻找符合条件的组
            if ((long) nums.get(i) + nums.get(n - 1) + nums.get(n - 2) + nums.get(
                        n - 3) < target) {
                continue;
            }
            for (int j = i + 1; j < n - 2; j++) {
                //第二个数原理相同
                if (j > i + 1 && nums.get(j).equals(nums.get(j - 1))) {
                    continue;
                }
                if ((long) nums.get(i) + nums.get(j) + nums.get(j + 1) + nums.get(
                            j + 2) > target) {
                    break;
                }
                if ((long) nums.get(i) + nums.get(j) + nums.get(n - 1) + nums.get(
                            n - 2) < target) {
                    continue;
                }
                //双指针遍历存在区间
                int left = j + 1, right = n - 1;
                while (left < right) {
                    int sum = nums.get(i) + nums.get(j) + nums.get(left) + nums.get(right);
                    //双指针遍历找到满足条件的组
                    //防止所有元素相同
                    if (sum == target) {
                        ArrayList<Integer> list = new ArrayList<>();
                        list.add(nums.get(i));
                        list.add(nums.get(j));
                        list.add(nums.get(left));
                        list.add(nums.get(right));
                        res.add(list);
                        //left和right去重，同时由于left和right的值已经加入集合，需要额外移动一次指针，找到新值
                        while (left < right && nums.get(left).equals(nums.get(left + 1))) {
                            left++;
                        }
                        left++;
                        while (left < right && nums.get(right).equals(nums.get(right - 1))) {
                            right--;
                        }
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return res;
    }
}