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:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• 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)

思路：转换成2Sum，注意跟3Sum一样先排序去重。

import java.util.ArrayList;import java.util.Arrays;public class Solution {	public ArrayList
    
     
      > fourSum(int[] num, int target) {		ArrayList
      
       
        > result = new ArrayList
        
         
          >(); if (num == null || num.length < 4) return result; int n = num.length; Arrays.sort(num); int i, j, start, end, sum; for (i = 0; i < n - 3; i++) { for (j = i + 1; j < n - 2; j++) { start = j + 1; end = n - 1; while (start < end) { sum = num[start] + num[end]; if (sum < target - num[i] - num[j]) start++; else if (sum > target - num[i] - num[j]) end--; else { ArrayList
          
            tmp = new ArrayList
           
            (); tmp.add(num[i]); tmp.add(num[j]); tmp.add(num[start]); tmp.add(num[end]); result.add(tmp); start++; end--; while (start < j && num[start - 1] == num[start]) start++; while (end >= j + 1 && num[end + 1] == num[end]) end--; } } while (j < n - 1 && num[j] == num[j + 1]) j++; } while (i < n - 1 && num[i] == num[i + 1]) i++; } return result; } public static void main(String[] args) { System.out.println(new Solution().fourSum(new int[] { 1, 0, -1, 0, -2, 2 }, 0)); }}