问题

给定一个包含n个整数的数组nums和一个目标值target，判断nums中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与target相等？找出所有满足条件且不重复的四元组
注意：答案中不可以包含重复的四元组

示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：
输入：nums = [], target = 0
输出：[]

思路

四数之和，和三数之和是一个思路，都是使用双指针法，基本解法就是在三数之和的基础上再套一层for循环。
需要注意，不要判断nums[j] > target就返回了，三数之和可以通过nums[i] > 0就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值
三数之和的双指针解法是一层for循环，num[i]为确定值，然后循环内有left和right作为双指针，找到nums[i] + nums[left] + nums[right] == 0
四数之和的双指针解法是两层for循环，nums[i] + nums[j]为确定值，依然是循环内有left和right作为双指针，找出nums[i] + nums[j] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是leetcode-18：四数之和 - 图1，四数之和的时间复杂度是leetcode-18：四数之和 - 图2

对于三数之和双指针法就是将原本暴力leetcode-18：四数之和 - 图3的解法，降为leetcode-18：四数之和 - 图4的解法，四数之和的双指针解法就是将原本暴力leetcode-18：四数之和 - 图5的解法，降为leetcode-18：四数之和 - 图6的解法

具体实现时，还可以进行一些剪枝操作：

  • 在确定第一个数之后，如果 leetcode-18：四数之和 - 图7，说明此时剩下的三个数无论取什么值，四数之和一定大于target，因此退出第一重循环
  • 在确定第一个数之后，若 leetcode-18：四数之和 - 图8，说明此时剩下的三个数无论取什么值，四数之和一定小于target，因此第一重循环直接进入下一轮，枚举leetcode-18：四数之和 - 图9
  • 在确定前两个数之后，如果leetcode-18：四数之和 - 图10，说明此时剩下的两个数无论取什么值，四数之和一定大于target，因此退出第二重循环
  • 在确定前两个数之后，如果leetcode-18：四数之和 - 图11，说明此时剩下的两个数无论取什么值，四数之和一定小于target，因此第二重循环直接进入下一轮，枚举 leetcode-18：四数之和 - 图12

解法

  1. package leetcode_18;
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.List;
  7. public class solution {
  8.     public List<List<Integer>> fourSum(int[] nums, int target){
  9.         List<List<Integer>> quadruplets = new ArrayList<>();
  10.         if(nums == null || nums.length < 4){
  11.             return quadruplets;
  12.         }
  14.         Arrays.sort(nums);
  15.         int length = nums.length;
  16.         for(int i = 0; i < length - 3; i++){
  17.             if(i > 0 && nums[i] == nums[i-1]){
  18.                 continue;
  19.             }
  20.             if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
  21.                 break;
  22.             }
  23.             if (nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
  24.                 continue;
  25.             }
  26.             for(int j = i + 1; j < length - 2; j++){
  27.                 if (j > i + 1 && nums[j] == nums[j - 1]) {
  28.                     continue;
  29.                 }
  30.                 if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
  31.                     break;
  32.                 }
  33.                 if (nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
  34.                     continue;
  35.                 }
  36.                 int left = j + 1;
  37.                 int right = length - 1;
  38.                 while(left < right){
  39.                     int sum = nums[i] + nums[j] + nums[left] + nums[right];
  40.                     if(sum == target){
  41.                         quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
  42.                         while (left < right && nums[left] == nums[left + 1]){
  43.                             left++;
  44.                         }
  45.                         left++;
  46.                         while (left < right && nums[right] == nums[right - 1]){
  47.                             right--;
  48.                         }
  49.                         right--;
  50.                     }
  51.                     else if(sum < target){
  52.                         left++;
  53.                     }
  54.                     else{
  55.                         right--;
  56.                     }
  57.                 }
  58.             }
  59.         }
  60.         return quadruplets;
  61.     }
  62. }
  1. class Solution {
  2. public:
  3.     vector<vector<int>> fourSum(vector<int>& nums, int target) {
  4.         vector<vector<int>> result;
  5.         sort(nums.begin(), nums.end());
  6.         for (int k = 0; k < nums.size(); k++) {
  7.             // 这种剪枝是错误的，这道题目target 是任意值 
  8.             // if (nums[k] > target) {
  9.             //     return result;
  10.             // }
  11.             // 去重
  12.             if (k > 0 && nums[k] == nums[k - 1]) {
  13.                 continue;
  14.             }
  15.             for (int i = k + 1; i < nums.size(); i++) {
  16.                 // 正确去重方法
  17.                 if (i > k + 1 && nums[i] == nums[i - 1]) {
  18.                     continue;
  19.                 }
  20.                 int left = i + 1;
  21.                 int right = nums.size() - 1;
  22.                 while (right > left) {
  23.                     if (nums[k] + nums[i] + nums[left] + nums[right] > target) {
  24.                         right--;
  25.                     } else if (nums[k] + nums[i] + nums[left] + nums[right] < target) {
  26.                         left++;
  27.                     } else {
  28.                         result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
  29.                         // 去重逻辑应该放在找到一个四元组之后
  30.                         while (right > left && nums[right] == nums[right - 1]) right--;
  31.                         while (right > left && nums[left] == nums[left + 1]) left++;
  33.                         // 找到答案时，双指针同时收缩
  34.                         right--;
  35.                         left++;
  36.                     }
  37.                 }
  39.             }
  40.         }
  41.         return result;
  42.     }
  43. };

拓展——Arrays.asList()

该方法是将数组转化成List集合的方法：List<String> list = Arrays.asList("a","b","c");

注意：

  • 该方法适用于对象型数据的数组（String、Integer…）
  • 该方法不建议使用于基本数据类型的数组（byte, short, int, long, float, double, boolean）
  • 该方法将数组与List列表链接起来：当更新其一个时，另一个自动更新
  • 不支持add()、remove()、clear()等方法

用此方法得到的List的长度是不可改变的：

  • 当你向这个List添加或删除一个元素时（例如 list.add(“d”);）程序就会抛出异常java.lang.UnsupportedOperationException
  • public static <T> List<T> asList(T... a) {return new ArrayList<>(a);}，当你看到这段代码时可能觉得没啥问题啊，不就是返回了一个ArrayList对象吗？问题就出在这里
  • 这个ArrayList不是java.util包下的，而是java.util.Arrays.ArrayList，它是Arrays类自己定义的一个静态内部类，这个内部类没有实现add()、remove()方法，而是直接使用它的父类AbstractList的相应方法。而AbstractList中的add()和remove()是直接抛出java.lang.UnsupportedOperationException异常的！

总结：

  • 如果你的List只是用来遍历，就用Arrays.asList()
  • 如果你的List还要添加或删除元素，还是乖乖地new一个java.util.ArrayList，然后一个一个的添加元素
import java.util.Arrays;
import java.util.List;

public class Test {
    public static void main(String[] args){

       //1、对象类型(String型)的数组数组使用asList()，正常
        String[] strings = {"aa", "bb", "cc"};
        List<String> stringList = Arrays.asList(strings);
        System.out.print("1、String类型数组使用asList()，正常：  ");
        for(String str : stringList){
            System.out.print(str + " ");
        }
        System.out.println();


        //2、对象类型(Integer)的数组使用asList()，正常
        Integer[] integers = new Integer[] {1, 2, 3};
        List<Integer> integerList = Arrays.asList(integers);
        System.out.print("2、对象类型的数组使用asList()，正常：  ");
        for(int i : integerList){
            System.out.print(i + " ");
        }
//      for(Object o : integerList){
//          System.out.print(o + " ");
//      }
        System.out.println();


        //3、基本数据类型的数组使用asList()，出错
        int[] ints = new int[]{1, 2, 3};
        List intList = Arrays.asList(ints);
        System.out.print("3、基本数据类型的数组使用asList()，出错(输出的是一个引用，把ints当成一个元素了)：");
        for(Object o : intList){
            System.out.print(o.toString());
        }
        System.out.println();

        System.out.print("   " + "这样遍历才能正确输出：");
        int[] ints1 = (int[]) intList.get(0);
        for(int i : ints1){
            System.out.print(i + " ");
        }
        System.out.println();

        //4、当更新数组或者List,另一个将自动获得更新
        System.out.print("4、当更新数组或者List,另一个将自动获得更新：  ");
        integerList.set(0, 5);
        for(Object o : integerList){
            System.out.print(o + " ");
        }
        for(Object o : integers){
            System.out.print (o + " ");
        }
        System.out.println();

        //5、add()   remove() 报错
        System.out.print("5、add()   remove() 报错：  ");
//      integerList.remove(0);
//      integerList.add(3, 4);
//      integerList.clear(); 
    }
}

1、String类型数组使用asList()，正常：  aa bb cc 
2、对象类型的数组使用asList()，正常：  1 2 3 
3、基本数据类型的数组使用asList()，出错(输出的是一个引用，把ints当成一个元素了)：[I@4554617c
   这样遍历才能正确输出：1 2 3 
4、当更新数组或者List,另一个将自动获得更新：  5 2 3 5 2 3 
5、add()、remove()、clear() 报错：