nSum问题解题套路

Java leetcode
数据结构与算法
发布日期:   2022-09-09

4.5 2sum问题的核心思想

4.5.1 2SUM-1

  • 给你输入一个数组nums和target可以保证在数组存在两个数的和为target，请你返回这两个数的索引

直接的想法是穷举任意两个数的组合，然后去试验符不符合要求，如果想要让时间复杂度下降，一般的方法就是用空间换时间，可以通过一个哈希表记录元素值到索引的映射，减少时间复杂度

private Map<Integer,Integer> map = new HashMap<>();
public int[] twoSum(int[] nums, int target) {
    for(int i = 0;i<nums.length;i++){
        map.put(nums[i],i);
    }
    for(int i = 0;i<nums.length;i++){
        int other = target - nums[i];
        //如果other存在而且不是nums[i]本身,那么就返回这两个索引
        if(map.containsKey(other) && map.get(other) != i){
            return new int[]{i,map.get(other)};
        }
    }
    return new int[]{-1,-1};
}
  • 复杂度分析:这样，由于哈希表的查询时间为O(1)，算法的时间复杂度降低到O(N),但是需要O(N)的空间复杂度来存储哈希表。

4.5.2 2SUM-2

这里稍微修改一下前面的问题，设计一个类，拥有两个API:

private Map<Integer,Integer> freq = new HashMap<>();
public void add(int number){
    //记录number出现的次数
    freq.put(number,freq.getOrDefault(number,0)+1);
}
public boolean find(int value){
    for (Integer key : freq.keySet()) {
        int other = value - key;
        //情况一
        if(other == key && freq.get(key) >1){
            return true;
        }
        //情况二
        if(other!=key && freq.containsKey(other) ){
            return true;
        }
    }
    return false;
}
  • 涉及到find的时候有两种情况
    • 情况一:add了[3,3,2,5]之后，执行find(6)，由于3出现了两次，3+3=3，所以返回true
    • 情况二:add了[3,3,2,5]之后，执行find(7)，那么当key为2,other为5的时候，算法返回true
    • 复杂度分析:add的操作的时间复杂度为O(1),find方法的时间复杂度为O(N),空间复杂度均为O(N)
  • 对于频繁使用find方法的场景，可以尝试借助哈希集合来有针对性地优化find方法
Set<Integer> sum = new HashSet<>();
List<Integer> nums = new ArrayList<>();
public void add(int number){
    //记录所有可能组成的和
    for (Integer n : nums) {
        sum.add(n+number);
    }
    nums.add(number);
}
public boolean find(int value){
    return sum.contains(value);
}

这样sum中存储了所有加入数字可能组成的和，每次find只需要花费O(1)的时间在集合中判断是否存在，但是代价也很明显，最坏情况下add后sum的大小都会翻一倍，所以空间复杂度是O(2^N)

4.5.3 最后总结

对于2sum问题，一个难点就是给的数组无序，对于一个无序的数组，似乎只能暴力穷举所有的可能

一般情况下，我们会首先把数组排序再考虑双指针到的技巧，2Sum启发我们，HashMap或者HashSet也可以帮助我们处理无序数组的相关问题，如果给定的数组是有序的，那么算法应该这样写

public int[] twoSum(int[] nums, int target) {
    int left = 0,right = nums.length-1;
    while(left<right){
        int sum = nums[left] + nums[right];
        if(target == sum){
            return new int[]{left,right};
        }else if(sum <target){
            left++;
        }else if(sum > target){
            right++;
        }
    }
    return new int[]{-1,-1};
}

4.6 一个函数解决nSum问题

4.6.1 问题泛化

  • 假设输入一个数组nums和一个目标target，请返回nums中能够凑出target的两个元素的值，比如输入nums=[1,3,5,6],target=9，那么算法返回两个元素[3,6]，假设有且只有一对元素可凑出target

这个问题可以先对nums进行排序，然后双指针向中间逼近就可以了

  • 问题泛化:nums中可能有多对元素之和等于target，请返回所有和为target的元素对，其中不能出现重复

对于修改之和的问题，关键难点是选择可能有多个和为target的数对，还不能重复，比如说[1,3]和[3,1]就算重复，只能算一次

首先，对于这道题而言基本思路还是双指针+排序，先初步写出代码

List<List<Integer>> twoSumTarget(int[] nums,int target){
    Arrays.sort(nums);//先对数组进行排序
    List<List<Integer>> ans = new ArrayList<>();
    int left = 0,right = nums.length-1;
    while(left<right){
        int sum = nums[left] + nums[right];
        //根据sum和target的比较,移动左右指针
        if(sum<target){
            left++;
        }
        if(sum>target){
            right++;
        }
        if(sum == target){
            List<Integer> t = new ArrayList<>();
            t.add(left);t.add(right);
            ans.add(t);
            left++;right--;
        }
    }
    return ans;
}

但是，这样实现肯定会造成重复的结果，比如说nums=[1,1,1,2,2,3,3],target=4，得到的结果中[1,3]是肯定会重复的

问题处在sum == target的if条件分支，当给res加入一次结果后,left和right在改变1的同时，还应该跳过所有重复的元素，也就是说看它移动的下一个位置的元素，是不是和当前的值一样，当然了，有的可能会有这种想法，新建一个set来保证元素不重复不就可以了吗，当然是可以，但是这样做依然无法避免大量的重复不必要计算。

if(sum == target){
    List<Integer> t = new ArrayList<>();
    t.add(left);t.add(right);
    ans.add(t);
    //跳过所有的重复元素
    while(left<right && nums[left] == leftVal){
        left++;
    }
    while (left<right && nums[right] == rightVal){
        right--;
    }
}

这样就可以保证一个答案只被添加一次，重复的结果都会被跳过，可以得到正确答案，那么前面的两个if分支也可以做一下这种优化，跳过相同的元素。完整代码如下:

List<List<Integer>> twoSumTarget(int[] nums,int target){
    Arrays.sort(nums);//先对数组进行排序
    List<List<Integer>> ans = new ArrayList<>();
    int left = 0,right = nums.length-1;
    while(left<right){
        int sum = nums[left] + nums[right];
        int leftVal = nums[left];
        int rightVal = nums[right];
        //根据sum和target的比较,移动左右指针
        if(sum<target){
            while(left<right && nums[left] == leftVal){
                left++;
            }
        }
        if(sum>target){
            while (left<right && nums[right] == rightVal){
                right--;
            }
        }
        if(sum == target){
            List<Integer> t = new ArrayList<>();
            t.add(left);t.add(right);
            ans.add(t);
            //跳过所有的重复元素
            while(left<right && nums[left] == leftVal){
                left++;
            }
            while (left<right && nums[right] == rightVal){
                right--;
            }
        }
    }
    return ans;
}
  • 复杂度分析:双指针操作的时间复杂度为O(N)，排序的时间复杂度为O(NlogN)，时间复杂度为O(NlogN)

4.6.2 解决3Sum问题

  • 给你输入一个数组nums，请你判断其中是否存在三个元素a,b,c使得a+b+c=0，如果有的话请找出所有满足条件而且不重复的三元组

这个问题的解决思路可以这样思考,首先三个数，第一个数字我们可以通过穷举nums[i]的任意一个元素来得到，后面两个元素转换为target-nums[i]，然后再把这个target-nums[i]作为新的target丢到2Sum问题去解决就可以了

public List<List<Integer>> threeSum(int[] nums) {
    return threeSumTarget(nums,0);
}

public List<List<Integer>> threeSumTarget(int[] nums,int target){
    //输入数组nums,返回所有和为target的三元组
    Arrays.sort(nums);
    int n = nums.length;
    List<List<Integer>> ans = new ArrayList<>();
    //穷举threeSum的第一个数
    for(int i = 0;i<n;i++){
        //对target-nums[i]计算twoSum
        List<List<Integer>> tuples = twoSumTarget(nums, target - nums[i], i + 1);
        //如果存在满足条件的二元组,再加上nums[i]就是符合条件的三元组
        for (List<Integer> tuple : tuples) {
            tuple.add(nums[i]);
            ans.add(new ArrayList<>(tuple));
        }
        //跳过第一个数字重复的情况,否则会出现重复的结果
        while(i<n-1 && nums[i] == nums[i+1]){
            i++;
        }
    }
    return ans;
}

/**
 *
 * @param nums
 * @param target
 * @param start
 * @return
 */
List<List<Integer>> twoSumTarget(int[] nums,int target,int start){//左指针改为从start开始,其他不变
    List<List<Integer>> ans = new ArrayList<>();
    int left = start,right = nums.length-1;
    while(left<right){
        int sum = nums[left] + nums[right];
        int leftVal = nums[left];
        int rightVal = nums[right];
        //根据sum和target的比较,移动左右指针
        if(sum<target){
            while(left<right && nums[left] == leftVal){
                left++;
            }
        }
        if(sum>target){
            while (left<right && nums[right] == rightVal){
                right--;
            }
        }
        if(sum == target){
            List<Integer> t = new ArrayList<>();
            t.add(leftVal);t.add(rightVal);
            ans.add(t);
            //跳过所有的重复元素
            while(left<right && nums[left] == leftVal){
                left++;
            }
            while (left<right && nums[right] == rightVal){
                right--;
            }
        }
    }
    return ans;
}
  • 复杂度分析:排序的时间复杂度为O(NlogN),双指针操作为O(N),函数在for循环中调用twoSumTarget,所以就是O(NlogN+N^2)=O(N^2)

4.6.3 解决4Sum问题

  • 4Sum的解决思路也是一致的，只需要加上一个穷举nums[i]的过程即可
public List<List<Integer>> fourSum(int[] nums, int target) {
    return fourSumTarget(nums,target);
}

public List<List<Integer>> fourSumTarget(int[] nums,long target){
    Arrays.sort(nums);
    List<List<Integer>> ans = new ArrayList<>();
    for(int i = 0;i<nums.length;i++){
        List<List<Integer>> tuples = threeSumTarget(nums,target-(long)nums[i],i+1);
        for (List<Integer> tuple :tuples){
            tuple.add(nums[i]);
            ans.add(new ArrayList<>(tuple));
        }
        while(i<nums.length-1 && nums[i] == nums[i+1]){
            i++;
        }
    }
    return ans;
}


public List<List<Integer>> threeSumTarget(int[] nums,long target,int start){
    //输入数组nums,返回所有和为target的三元组
    int n = nums.length;
    List<List<Integer>> ans = new ArrayList<>();
    //穷举threeSum的第一个数
    for(int i = start;i<n;i++){
        //对target-nums[i]计算twoSum
        List<List<Integer>> tuples = twoSumTarget(nums, (target - (long)nums[i]), i + 1);
        //如果存在满足条件的二元组,再加上nums[i]就是符合条件的三元组
        for (List<Integer> tuple : tuples) {
            tuple.add(nums[i]);
            ans.add(new ArrayList<>(tuple));
        }
        //跳过第一个数字重复的情况,否则会出现重复的结果
        while(i<n-1 && nums[i] == nums[i+1]){
            i++;
        }
    }
    return ans;
}

/**
 *
 * @param nums
 * @param target
 * @param start
 * @return
 */
List<List<Integer>> twoSumTarget(int[] nums,long target,int start){//左指针改为从start开始,其他不变
    List<List<Integer>> ans = new ArrayList<>();
    int left = start,right = nums.length-1;
    while(left<right){
        long sum = nums[left] + nums[right];
        long leftVal = nums[left];
        long rightVal = nums[right];
        //根据sum和target的比较,移动左右指针
        if(sum<target){
            while(left<right && nums[left] == leftVal){
                left++;
            }
        }
        if(sum>target){
            while (left<right && nums[right] == rightVal){
                right--;
            }
        }
        if(sum == target){
            List<Integer> t = new ArrayList<>();
            t.add((int)leftVal);t.add((int)rightVal);
            ans.add(t);
            //跳过所有的重复元素
            while(left<right && nums[left] == leftVal){
                left++;
            }
            while (left<right && nums[right] == rightVal){
                right--;
            }
        }
    }
    return ans;
}
  • 注意一组样例:[1000000000,1000000000,1000000000,1000000000] -294967296这组样例是新加的，如果只是用int的话就会溢出，在涉及到加减的地方该为long的数据类型即可解决该问题

4.6.4 解决nSum问题

  • 让我们回想一下刚才的解题过程，有没有发现其实除了2Sum以外，更高次数的sum都是基于2Sum来做枚举的?而且问题的解决办法都是一样的?
  • 所以可以得出结论:base-case:2Sum,通过不断转移数组下标来转移状态，
//注意:调用这个函数之前,nums必须是排好序的
List<List<Integer>> nSumTarget(int[] nums,int n,int start,long target){
    int size = nums.length;
    List<List<Integer>> ans =  new ArrayList<>();
    //至少是2Sum而且,而且数组大小不能小于n
    if(n<2 || size<n) {
        return ans;
    }
    //base-case
    if(n==2){
        int lo = start ,hi = size-1;
        while(lo < hi){
            long sum = (long)nums[lo] + (long)nums[hi];
            int left = nums[lo];int right = nums[hi];
            if(sum< target){
                while (lo<hi && nums[lo] == left){
                    lo++;
                }
            }else if(sum > target){
                while (lo<hi && nums[hi] == right){
                    hi--;
                }
            }else {
                List<Integer> t = new ArrayList<>();
                t.add(left);t.add(right);
                while (lo<hi && nums[lo] == left){
                    lo++;
                }
                while (lo<hi && nums[hi] == right){
                    hi--;
                }
            }
        }
    }else{
        //n>2的时候直接递归计算即可
        for(int i = start;i<size;i++){
            List<List<Integer>> tuples = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
            for (List<Integer> tuple : tuples) {
                tuple.add(nums[i]);
                ans.add(new ArrayList<>(tuple));
            }
            while (i<size-1 && nums[i] == nums[i+1]){
                i++;
            }
        }
    }
    ret
文章作者: 穿山甲
文章链接: https://lumxi.github.io/2022/09/09/algorithm/labuladong/4.5-4.6note/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 穿山甲 !
Java leetcode
赏
  目录