2Sum

在分析多数和之前，请先看Two Sum的详解

3Sum

双指针法

复杂度

时间 O(N^2) 空间 O(1)

思路

3Sum其实可以转化成一个2Sum的题，我们先从数组中选一个数，并将目标数减去这个数，得到一个新目标数。然后再在剩下的数中找一对和是这个新目标数的数，其实就转化为2Sum了。为了避免得到重复结果，我们不仅要跳过重复元素，而且要保证2Sum找的范围要是在我们最先选定的那个数之后的。

代码

public class Solution {    public List<List<Integer>> threeSum(int[] nums) {        Arrays.sort(nums);        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();        for(int i = 0; i < nums.length - 2; i++){// 跳过重复元素if(i > 0 && nums[i] == nums[i-1]) continue;// 计算2SumArrayList<List<Integer>> curr = twoSum(nums, i, 0 - nums[i]);res.addAll(curr);        }        return res;    }        private ArrayList<List<Integer>> twoSum(int[] nums, int i, int target){        int left = i + 1, right = nums.length - 1;        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();        while(left < right){if(nums[left] + nums[right] == target){    ArrayList<Integer> curr = new ArrayList<Integer>();    curr.add(nums[i]);    curr.add(nums[left]);    curr.add(nums[right]);    res.add(curr);    do {        left++;    }while(left < nums.length && nums[left] == nums[left-1]);    do {        right--;    } while(right >= 0 && nums[right] == nums[right+1]);} else if (nums[left] + nums[right] > target){    right--;} else {    left++;}        }        return res;    }}

4Sum

双指针法

复杂度

时间 O(N^3) 空间 O(1)

思路

和3Sum的思路一样，在计算4Sum时我们可以先选一个数，然后在剩下的数中计算3Sum。而计算3Sum则同样是先选一个数，然后再剩下的数中计算2Sum。

代码

public class Solution {    public List<List<Integer>> fourSum(int[] nums, int target) {        Arrays.sort(nums);        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();        for(int i = 0; i < nums.length - 3; i++){if(i > 0 && nums[i] == nums[i-1]) continue;List<List<Integer>> curr = threeSum(nums, i, target - nums[i]);res.addAll(curr);        }        return res;    }        private List<List<Integer>> threeSum(int[] nums, int i, int target) {        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();        for(int j = i + 1; j < nums.length - 2; j++){if(j > i + 1 && nums[j] == nums[j-1]) continue;List<List<Integer>> curr = twoSum(nums, i, j, target - nums[j]);res.addAll(curr);        }        return res;    }        private ArrayList<List<Integer>> twoSum(int[] nums, int i, int j, int target){        int left = j + 1, right = nums.length - 1;        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();        while(left < right){if(nums[left] + nums[right] == target){    ArrayList<Integer> curr = new ArrayList<Integer>();    curr.add(nums[i]);    curr.add(nums[j]);    curr.add(nums[left]);    curr.add(nums[right]);    res.add(curr);    do {        left++;    }while(left < nums.length && nums[left] == nums[left-1]);    do {        right--;    } while(right >= 0 && nums[right] == nums[right+1]);} else if (nums[left] + nums[right] > target){    right--;} else {    left++;}        }        return res;    }}