18.四数之和

[rocksc30]

为了快速通过，直接把15题三数之和的代码贴过来，改了target的数据类型int-->long，因为这道题有一个用例会导致数据溢出， 这个解法的效率一般。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        long t = target;
        for (int i = 0; i < nums.length - 1; i++) {
            List<List<Integer>> list = threeSum(nums, t - nums[i], i + 1);
            int sum = 0;
            for (List<Integer> tuple : list) {
                tuple.add(nums[i]);
                ans.add(tuple);
            }
            while (i < nums.length - 1 && nums[i] == nums[i+1]){
                i++;
            }
        }
        return ans;
    }
    public List<List<Integer>> threeSum(int[] nums, long target, int start) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = start; i < nums.length - 1; i++) {
            List<List<Integer>> list = twoSum(nums, target - nums[i], i + 1);
            for (List<Integer> tuple : list) {
                tuple.add(nums[i]);
                ans.add(tuple);
            }
            while (i < nums.length - 1 && nums[i] == nums[i+1]){
                i++;
            }
        }
        return ans;
    }

    public List<List<Integer>> twoSum(int[] nums, long target, int start){
        // 排序 + 双指针
        Arrays.sort(nums);
        int left = start, right = nums.length - 1;
        List<List<Integer>> ans = new ArrayList<>();

        while(left < right){
            int sum = nums[left] + nums[right];
            int leftNum = nums[left], rightNum = nums[right];
            if (sum > target){
                while (right > left && nums[right] == rightNum){
                    right--;
                }
            } else if (sum < target){
                while (left < right && nums[left] == leftNum){
                    left++;
                }
            } else {
                List<Integer> one = new ArrayList<>();
                one.add(nums[left]);
                one.add(nums[right]);
                ans.add(one);
                right--;
                left++;
                while (right > left && nums[right] == rightNum){
                    right--;
                }
                while (left < right && nums[left] == leftNum){
                    left++;
                }
            }
        }
        return ans;
    }
}