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]]

难度：medium

题目：

给定一整数数组和一目标整数，是否存在4个数的和为指定整数？ 找出所有这样不同的4元组。注意：答案一定不能包含重复的四元组。

思路：

数组排序，固定一个数，然后降级为3sum

Runtime: 34 ms, faster than 78.86% of Java online submissions for 4Sum.

Memory Usage: 31.7 MB, less than 13.82% of Java online submissions for 4Sum.

class Solution {    public List
    
     
      > fourSum(int[] nums, int target) {        List
      
       
        > result = new ArrayList();        Arrays.sort(nums);        int numsLen = nums.length;        for (int k = 0; k < numsLen; k++) {            if (0 == k || nums[k - 1] != nums[k]) {                for (int i = k + 1; i < numsLen; i++) {                    if ((k + 1) == i || nums[i - 1] != nums[i]) {                        for (int left = i + 1, right = numsLen - 1; left < right; left++, right--) {                            int sum = nums[left] + nums[right] + nums[i] + nums[k];                            if (target == sum                                 && ((i + 1) == left || nums[left - 1] != nums[left])                                && ((numsLen - 1) == right || nums[right] != nums[right + 1])                               ) {                                result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));                            } else if (sum > target) {                                left--;                            } else {                                right++;                            }                        }                    }                        }            }        }        return result;    }}