这道4Sum，如果用3Sum类似的方法，是O(n^3)的复杂度。现在使用O(n^2)的空间呢，能达到O(n^2)的时间复杂度。但实现起来坑还是不少，一是要去重，用了string来表示集合的key；二是不能同一个索引位置的数（num[i]）出现两次，所以要做下标的检查；三是当左右相加等于target的时候，现在不能直接跳过大小一样的，因为同样大小的可能是a+b也可能是c+d，就要l++和r--递归来做。但用递归有可能爆栈（Runtime Error），就用了Stack来模拟递归。最终Java 1472ms过。

后来参考方勤的版本，如果用map来存sum=>pair，在只求解（而非全部解）的情况下，可以O(n^2)写得更简洁。

import java.util.*;public class Solution {    private ArrayList
     
      
       > ans = new ArrayList
       
        
         >();    private HashSet
         
           ansSet = new HashSet
          
           (); private HashSet
           
             posSet = new HashSet
            
             (); public ArrayList
             
              
               > fourSum(int[] num, int target) { ans.clear(); ansSet.clear(); posSet.clear(); Arrays.sort(num); int len = num.length; ArrayList
               
                 pairs = new ArrayList
                
                 (); for (int i = 0; i < len; i++) { for (int j = i+1; j < len; j++) { pairs.add(new Pair(num[i], num[j], i, j)); } } Collections.sort(pairs); Stack
                 
                   stack = new Stack
                  
                   (); stack.push(0); stack.push(pairs.size()-1); while (!stack.empty()) { int r = stack.pop(); int l = stack.pop(); if (l >= r) continue; String posKey = "" + l + "_" + r; if (posSet.contains(posKey)) continue; else posSet.add(posKey); int sum = pairs.get(l).sum + pairs.get(r).sum; if (sum < target) { stack.push(l+1); stack.push(r); } else if (sum > target) { stack.push(l); stack.push(r-1); } else // == { if (pairs.get(l).aIdx != pairs.get(r).aIdx && pairs.get(l).aIdx != pairs.get(r).bIdx && pairs.get(l).bIdx != pairs.get(r).aIdx && pairs.get(l).bIdx != pairs.get(r).bIdx) { // add to result; ArrayList
                   
                     arr = new ArrayList
                    
                     (); arr.add(pairs.get(l).a); arr.add(pairs.get(l).b); arr.add(pairs.get(r).a); arr.add(pairs.get(r).b); Collections.sort(arr); String key = ""; for (int k = 0; k < 4; k++) { key = key + arr.get(k) + "_"; } if (!ansSet.contains(key)) { ansSet.add(key); ans.add(arr); } } stack.push(l); stack.push(r-1); stack.push(l+1); stack.push(r); } } return ans; }}class Pair implements Comparable
                     
                      { int a; int b; int sum; int aIdx; int bIdx; public Pair (int a, int b, int aIdx, int bIdx) { this.a = a; this.b = b; this.sum = a + b; this.aIdx = aIdx; this.bIdx = bIdx; } public int compareTo(Pair that) { return this.sum - that.sum; }}