LeetCode(18) － 4Sum

 1 public class Solution {
 2     public List<List<Integer>> fourSum(int[] nums, int target) {
 3         List<List<Integer>> res = new ArrayList<List<Integer>>();
 4         //先排序
 5         Arrays.sort(nums);
 6         for (int i = 0; i < nums.length - 3; i++) {
 7             //判断重复
 8             if (i != 0 && nums[i] == nums[i - 1]) continue;
 9             for (int j = i + 1; j < nums.length - 2; j++) {
10                 //判断重复
11                 if (j != i + 1 && nums[j] == nums[j - 1]) continue;
12                 int head = j + 1;
13                 int tail = nums.length - 1;
14                 while (head < tail) {
15                     //判断重复
16                     if (head != j+1 && nums[head] == nums[head - 1]) {
17                         head++;
18                         continue;
19                     }
20                     int sum = nums[i] + nums[j] + nums[head] + nums[tail];
21                     if (sum > target) tail--;
22                     else if (sum < target) head++;
23                     else {
24                         List<Integer> list = new ArrayList<Integer>();
25                         list.add(nums[i]);
26                         list.add(nums[j]);
27                         list.add(nums[head++]);
28                         list.add(nums[tail--]);
29                         res.add(list);
30                     }
31                 }
32             }
33         }
34         return res;
35     }
36 }