LeetCode(18) － 4Sum

　　思路和3Sum一样，只是把O(n^4)变成了O(n^3)，思路详细见3sum。最终能够ac。

　　代码如下：

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        //先排序
        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 head = j + 1;
                int tail = nums.length - 1;
                while (head < tail) {
                    //判断重复
                    if (head != j+1 && nums[head] == nums[head - 1]) {
                        head++;
                        continue;
                    }
                    int sum = nums[i] + nums[j] + nums[head] + nums[tail];
                    if (sum > target) tail--;
                    else if (sum < target) head++;
                    else {
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[head++]);
                        list.add(nums[tail--]);
                        res.add(list);
                    }
                }
            }
        }
        return res;
    }
}