春招冲刺Day5[高频算法题] --2SUm | 3Sum....N Sum问题

春招冲刺Day5[高频算法题] --2SUm | 3Sum....N Sum问题

一套模板解决Nsum问题

• 三数之和
• N数之和
• 管你几和,直接用模板秒杀
• • `三和`
  • `四和`

声明本文来自Labuladong大佬,本文只是用Java实现了一遍
这里贴上Labuladong大佬的原文
传送门

三数之和

三数之和

class Solution {
    public static List> threeSum(int[] nums) {
        List> res = new ArrayList<>();
        if(nums.length == 0 || nums == null) return res;
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            List> list = twoSum(nums, i+ 1, 0 - nums[i]);
            for (List temp : list) {
                temp.add(nums[i]);
                res.add(temp);
            }
            while(i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
        }
        return res;
    }

    public static List> twoSum(int [] nums,int start, int target){
        int l = start, h = nums.length - 1;
        Arrays.sort(nums);
        List> list = new ArrayList<>();
        while(l < h){
            int left = nums[l] , right = nums[h];
            int sum = left + right;
            if(sum < target) l++;
            else if(sum > target) h--;
            else{
                //要报错 list.add(Arrays.asList(nums[l],nums[h]));
                //错误原因 https://www.jianshu.com/p/9153c8cb1f3d
                list.add(new ArrayList<>(Arrays.asList(nums[l],nums[h])));
                while(l < h && nums[l] == left) l++;
                while(l < h && nums[h] == right) h--;
            }
        }
        return list;
    }
}

注意: 使用Arrays.asList时需要额外注意;
如果Arrays.asList的结果用List接收,那么在调用list.add()和remove方法时会报错,
原因

N数之和

N数之和 通用模板

// n 代表是几和  start: 从哪个数开始
    public static List> nSumTarget(int[] nums, int n, int start, int target){

        int size = nums.length;
        List> res = new ArrayList<>();

        //边界处理, 至少得2和,并且数组大小不应该小于n
        if(n < 2 || size < n) return res;

        //2sum问题 是base case
        if(n == 2){
            int l = start, h = nums.length - 1;
            while(l < h){
                int left = nums[l] , right = nums[h];
                int sum = left + right;
                if(sum < target) l++;
                else if(sum > target) h--;
                else{
                    res.add(new ArrayList<>(Arrays.asList(nums[l],nums[h])));
                    while(l < h && nums[l] == left) l++;
                    while(l < h && nums[h] == right) h--;
                }
            }
        }else{
            // n > 2时,递归计算 (n - 1) Sum
            for (int i = 0; i < size; i++) {
                List> lists = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                for (List temp : lists) {
                    temp.add(nums[i]);
                    res.add(temp);
                }
                while( i < size - 1 && nums[i] == nums[i + 1]) i++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {-1, 0, 1, 2, -1, -4};
        Arrays.sort(arr);
        List> lists = Solution.nSumTarget(arr,3, 0, 0);
        for (List list : lists) {
            System.out.println(list);
        }
    }

output

[-1, 2, -1]
[0, 1, -1]

管你几和,直接用模板秒杀 三和

class Solution {
    public static List> threeSum(int[] nums) {
        List> list = new ArrayList<>();
        if(nums.length == 0 || nums == null) return list;
        Arrays.sort(nums);
        return nSumTarget(nums,3,0,0);
    }

    public static List> nSumTarget(int[] nums, int n, int start, int target){
            int size = nums.length;
            List> res = new ArrayList<>();
            //边界处理, 至少得2和,并且数组大小不应该小于n
            if(n < 2 || size < n) return res;
            //2sum问题 是base case
            if(n == 2){
                int l = start, h = nums.length - 1;
                while(l < h){
                    int left = nums[l] , right = nums[h];
                    int sum = left + right;
                    if(sum < target) l++;
                    else if(sum > target) h--;
                    else{
                        res.add(new ArrayList<>(Arrays.asList(nums[l],nums[h])));
                        while(l < h && nums[l] == left) l++;
                        while(l < h && nums[h] == right) h--;
                    }
                }
            }else{
                // n > 2时,递归计算 (n - 1) Sum
                for (int i = start; i < size; i++) {
                    List> lists = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                    for (List temp : lists) {
                        temp.add(nums[i]);
                        res.add(temp);
                    }
                    while( i < size - 1 && nums[i] == nums[i + 1]) i++;
                }
            }
            return res;
    }
}

---

四和

class Solution {
    public List> fourSum(int[] nums, int target) {
        List> list = new ArrayList<>();
        if(nums.length == 0 || nums == null) return list;
        Arrays.sort(nums);
        return nSumTarget(nums,4,0,target);
    }

    public List> nSumTarget(int[] nums, int n, int start, int target){
            int size = nums.length;
            List> res = new ArrayList<>();
            //边界处理, 至少得2和,并且数组大小不应该小于n
            if(n < 2 || size < n) return res;
            //2sum问题 是base case
            if(n == 2){
                int l = start, h = nums.length - 1;
                while(l < h){
                    int left = nums[l] , right = nums[h];
                    int sum = left + right;
                    if(sum < target) l++;
                    else if(sum > target) h--;
                    else{
                        res.add(new ArrayList<>(Arrays.asList(nums[l],nums[h])));
                        while(l < h && nums[l] == left) l++;
                        while(l < h && nums[h] == right) h--;
                    }
                }
            }else{
                // n > 2时,递归计算 (n - 1) Sum
                for (int i = start; i < size; i++) {
                    List> lists = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                    for (List temp : lists) {
                        temp.add(nums[i]);
                        res.add(temp);
                    }
                    while( i < size - 1 && nums[i] == nums[i + 1]) i++;
                }
            }
            return res;
    }
}