LeetCode-array-4Sum

题目：
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]
]

和求三个和的题目差不多，多了个target值

思路和3Sum一样，这里用到double for循环，3Sum的时候是固定循环第i个数，让(i+1)和(数组.length-1)两指针向中间移动，
在4Sum中我这里也是用这样的思路，代码如下

import java.net.Inet4Address;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by Wangjianxin on 2017/7/5 0005.
 */
public class FourSum {

    public static void main(String[] args) {
        int [] s = {-1,0,-5,-2,-2,-4,0,1,-2};
        int t = -9;
        System.out.println(fourSum(s,t));
    }
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> lists = new LinkedList<List<Integer>>();
        int len = nums.length;

        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        for(int i = 0; i<len ;i ++){
            int start = i;

            //排重
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            if(nums.length < 4){
                break;
            }
            for(int j = i+1;j<len ;j++){

                int left1 = j;
                int left2 = j+1;
                int right = len-1;

                if(nums[0] >0){
                    break;
                }
                //排重
                if(j > i+1 && nums[j-1] == nums[j]){
                    continue;
                }

                while ( left1 < left2 && left2 < right){

                    int sum = nums[start] + nums[left1] + nums[left2] + nums[right];
                    if(sum > target){
                        right--;
                    }
                    if(sum < target){
                        left2 ++;
                    }
                    //排重 俩指针
                    if(left2 > j+1 && nums[left2] == nums[left2 - 1]){
                        left2 ++;
                    }
                    if(right < len - 1 && nums[right] == nums[right + 1]){
                        right --;
                    }
                    else if(sum == target){
                        List<Integer> list = new LinkedList<Integer>();
                        list.add(nums[start]);
                        list.add(nums[left1]);
                        list.add(nums[left2]);
                        list.add(nums[right]);
                        lists.add(list);
                        left2++;
                        right--;
                    }
                }
            }
        }
        return lists;
    }
}