18. 四数之和

解法一：排序+双指针

思路和15. 三数之和一样，再多嵌套一层循环。

import java.util.*;
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        final int n = nums.length;
        List<List<Integer>> ans = new LinkedList<>();
        Arrays.sort(nums);
        for (int first = 0; first < n - 3; ) {
            for (int second = first + 1; second < n - 2; ) {
                int fourth = n - 1;
                for (int third = second + 1; (third < n - 1) && (third < fourth); ) {
                    int sum = nums[first] + nums[second] + nums[third] + nums[fourth];
                    while ((sum > target) && (third < fourth)) {
                        sum -= nums[fourth];
                        --fourth;
                        sum += nums[fourth];
                    }
                    if (third >= fourth) {
                        break;
                    }
                    if (sum == target) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[first]);
                        list.add(nums[second]);
                        list.add(nums[third]);
                        list.add(nums[fourth]);
                        ans.add(list);
                    }
                    ++third;
                    while ((nums[third] == nums[third - 1]) && (third < fourth)) {
                        ++third;
                    }
                }
                ++second;
                while ((nums[second] == nums[second - 1]) && (second < n - 2)) {
                    ++second;
                }
            }
            ++first;
            while ((nums[first] == nums[first - 1]) && (first < n - 3)) {
                ++first;
            }
        }
        return ans;
    }
}