LeetCode 18 四数之和（难度：Medium）

雨点打透心脏的1/2处 2022-01-29 22:55 189阅读 0赞

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

**注意：**

**答案中不可以包含重复的四元组。**

Given an array `nums` of *n* integers and an integer `target`, are there elements *a*, *b*, *c*, and *d* in `nums` such that *a* + *b* + *c* + *d* = `target`? Find all unique quadruplets in the array which gives the sum of `target`.

**Note:**

The solution set must not contain duplicate quadruplets.

**Example:**

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
    
    A solution set is:
    [
      [-1,  0, 0, 1],
      [-2, -1, 1, 2],
      [-2,  0, 0, 2]
    ]

示例：

给定数组 nums = \[1, 0, -1, 0, -2, 2\]，和 target = 0。

满足要求的四元组集合为：  
\[  
  \[-1,  0, 0, 1\],  
  \[-2, -1, 1, 2\],  
  \[-2,  0, 0, 2\]  
\]  
此题与15题求三数之和思路是一样，所以可以转化为求三数之和的问题，降低复杂度。

package pers.leetcode;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    /**
     * 4Sum 四数之和
     * 难易程度：Medium
     *
     * @author jinghui.zhu
     * @date 2019/5/17 9:31
     */
    public class LeetCode18 {
    
        public static void main(String[] args) {
            int[] nums = {-3, -2, -1, 0, 0, 1, 2, 3};
            int target = 0;
            System.out.println("leetcode18：" + fourSum(nums, target));
        }
    
    
        public static 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 >= 1 && nums[i] == nums[i-1]){
                    continue;
                }
    
                int threeSum = target - nums[i];
    
                for (int j = i + 1; j < nums.length - 2; j++){
                    //去重
                    if (j-1 != i && nums[j] == nums[j-1]){
                        continue;
                    }
                    int k = j + 1;
                    int z = nums.length - 1;
    
                    while (k < z){
                        if (nums[j] + nums[k] + nums[z] > threeSum){
                            z--;
                        }else if (nums[j] + nums[k] + nums[z] < threeSum){
                            k++;
                        }else {
                            List<Integer> temp = new ArrayList<>();
                            temp.add(nums[i]);
                            temp.add(nums[j]);
                            temp.add(nums[k]);
                            temp.add(nums[z]);
                            result.add(temp);
                            z--;
                            k++;
                            //去重
                            while (nums[k] == nums[k-1] && k < nums.length - 1){
                                k++;
                            }
                            //去重
                            while (nums[z] == nums[z+1] && z > 0){
                                z--;
                            }
                        }
                    }
    
                }
            }
            return result;
        }
    }