• nSum问题解题套路4.5-4.6

    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};
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 复杂度分析:这样，由于哈希表的查询时间为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;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 涉及到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);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    这样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};
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    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;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    但是，这样实现肯定会造成重复的结果，比如说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--;
                }
            }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    这样就可以保证一个答案只被添加一次，重复的结果都会被跳过，可以得到正确答案，那么前面的两个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;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 复杂度分析:双指针操作的时间复杂度为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;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 复杂度分析:排序的时间复杂度为O(NlogN),双指针操作为O(N),函数在for循环中调用twoSumTarget,所以就是O(NlogN+N2)=O(N2)

    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;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 注意一组样例:[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++;
                }
            }
        }
       return ans;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
  • 相关阅读:
    小红书种草推广步骤是怎样的，小红书种草效果好吗？
    GBASE 8A v953报错集锦61--集群扩容过程中有节点 offline 是否会有影响
    Element UI库 之 el-input 赋值后不能删除，修改，输入
    mySQL创建表的基础命令
    C++中volatile使用注释（①不被编译器优化，②多线程安全，③修饰指针或变量注意事项）
    NTC 温度采样 二分查表及公式法
    论文阅读【3】Efficient Estimation of Word Representations in Vector Space
    Java开发树结构数据封装！
    install GitHub Desktop on ubuntu
    ReactNative 开发之旅: 项目配置与版本管理实践
  • 原文地址：https://blog.csdn.net/weixin_50340097/article/details/126545049