Related Topics：[Array][Hash Table][Two Pointers]
Similar Questions:[Two Sum][3Sum][4Sum II]

题目：Given an array S of n integers, are there elements a, b, c, and d in S 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.

For example, given array S = [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]
]

LeetCode中关于数字之和还有其他几道，分别是[Two Sum 两数之和]，[3Sum 三数之和]，[3Sum Closest 最近三数之和]，虽然难度在递增，但是整体的套路都是一样的，此题的O(n^3)解法的思路跟[3Sum 三数之和]基本没啥区别，就是多加了一层for循环，其他的都一样。

java解法：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res=new LinkedList<>();
        Arrays.sort(nums);
        int i=0;
        while(i<nums.length-3) {
            //当与前一个元素相同时，跳过该元素的检查。
            if(i==0||(i!=0&&(nums[i]!=nums[i-1]))) {
                int j=i+1;
                while(j<nums.length-2) {
                    if(j==i+1||(j!=i+1&&(nums[j]!=nums[j-1]))){
                        int lo=j+1;
                        int hi=nums.length-1;
                        int sum=target-nums[i]-nums[j];
                        while(lo<hi){
                            if(nums[lo]+nums[hi]==sum) {
                   res.add(Arrays.asList(nums[i],nums[j],nums[lo],nums[hi]));
                               lo++;hi--;
                                //如果该元素与前（后）一元素相同，则跳过元素
                                while(lo<hi&&nums[lo]==nums[lo-1]) lo++;
                                while(lo<hi&&nums[hi]==nums[hi+1]) hi--;
                            }else if(nums[lo]+nums[hi]<sum) {
                                lo++;
                            }else hi--;
                        }
                    }
                    j++;
                }
            }
            i++;
        }
        return res;
    }
}