// ! 血的教训!!!!!!!!!!!!!!!!!!!!!!!!!
 // ! 先判断数组下表是否越界再判断值的问题!!!!!!!!!!!!!
// @lc code=start
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList();
        if (nums.length < 4) {
            return list;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-3 ; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length-2 ; j++) {

                if (j > i+1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int j2 = j + 1;
                int k = nums.length - 1;
                int newTarget =target-nums[i]-nums[j];
                while (j2 < k) {
                    int sum=nums[j2]+nums[k];
                    if (sum == newTarget) {
                        list.add(Arrays.asList(nums[i], nums[j], nums[j2], nums[k]));
                        while (j2 < k&& nums[j2] == nums[j2 + 1] ) {
                            j2++;
                        }             
                        while (j2 < k&& nums[k] == nums[k - 1] ) {
                            k--;
                        }
                        j2++;
                        k--;
                    } else if (newTarget < sum) {
                        k--;
                    } else {
                        j2++;
                    }
                }
            }
        }
        return list;
    }
}