X

LEETCODE 1498. Number of Subsequences That Satisfy the Given Sum Condition 解题思路分析

题目大意:

满足条件的子序列数目

给你一个整数数组 nums 和一个整数 target

请你统计并返回 nums 中能满足其最小元素与最大元素的 小于或等于 target非空 子序列的数目。

由于答案可能很大,请将结果对 10^9 + 7 取余后返回。

示例 1:

输入:nums = [3,5,6,7], target = 9
输出:4
解释:有 4 个子序列满足该条件。
[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

示例 2:

输入:nums = [3,3,6,8], target = 10
输出:6
解释:有 6 个子序列满足该条件。(nums 中可以有重复数字)
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

示例 3:

输入:nums = [2,3,3,4,6,7], target = 12
输出:61
解释:共有 63 个非空子序列,其中 2 个不满足条件([6,7], [7])
有效序列总数为(63 - 2 = 61)

示例 4:

输入:nums = [5,2,4,1,7,6,8], target = 16
输出:127
解释:所有非空子序列都满足条件 (2^7 - 1) = 127

提示:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6
  • 1 <= target <= 10^6

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1498

解题思路分析:

这道题的思路是使用排序加排列组合的算法。核心逻辑是:如果当前子序列的最大值加上最小值的和小于等于target的话,那么,我们可以将该子序列分为2个部分,最小值min和其他others。那么子序列others的所有排列组合再加上min组成的序列一定符合题意。

例如:用list=[min,num1,num2,num3,num4,max]表示min+max<=target的一个子序列,这里序列长度为6,包含最小值的子数组为:
[min]、[min,num1]、[min,num2]、[min,num1,num2,num3]、[min,num1,max]等等,这样的子数组有2^(n-1)个。(即[num1,num2,num3,num4,max]的全排列(2^(n-1))-1个,加上只有[min]的子数组,加起来共2^(n-1)个)

解题时,我们先对数组进行排序,然后使用左右指针来确定一个区间,区间起始默认为整个数组范围。这样能够保证任何一个区间内首元素一定是区间最小值,尾元素一定是最大值。如果最小值与最大值之和大于target,我们将右指针向左移动一位。反之当前区间为一个合理区间,区间内所有包含最小值的子序列都是一个合理解,根据上文,这些合理解的个数为2^(n-1)个,n为当前区间的长度。将该个数累加至返回结果。并将左指针向右移动一位,重复执行上述逻辑,直到左指针大于右指针为止。

另外,对于java语言还有一处需要注意的地方,我们在求解幂运算时,使用Math#pow方法可能会出现long型越界,因此需要手动进行计算,即将2乘以n-1次。期间,每次相乘后将结果与1000000007求余即可解决越界问题。不过使用这种方式会导致另一个问题,由于对于每一个区间我们都要做n-1次乘法,这样效率会非常低,我们可以采用记忆数组,记录下已经计算过的幂运算结果,避免重复计算。

实现代码:

long[] memo; // 记忆数组
public int numSubseq(int[] nums, int target) {
    memo = new long[nums.length]; // 初始化记忆数组
    Arrays.sort(nums); // 将数组排序
    int left=0,right=nums.length-1; // 左右指针
    long res=0; // 返回结果
    while(left<=right){ // 循环每一个区间
        // 如果区间内最大值与最小值之和大于target
        if(nums[left]+nums[right]>target){
            right--; // 向做移动右指针
        }else{ // 合理区间
            // 将区间内包含min的左右排列组合数累加至返回结果
            res+=pow(right-left);
            // 左区间向右移动一格
            left++;
        }
    }
    return (int)(res%1000000007);
}

long pow(int time){
    if(time==0) return 1;
    if(memo[time]>0) return memo[time];
    long res=2*pow(time-1);
    res%=1000000007;
    memo[time]=res;
    return res;
}

本题解法执行时间为33ms。

Runtime: 33 ms, faster than 100.00% of Java online submissions for Number of Subsequences That Satisfy the Given Sum Condition.

Memory Usage: 59.7 MB, less than 100.00% of Java online submissions for Number of Subsequences That Satisfy the Given Sum Condition.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1498-number-of-subsequences-that-satisfy-the-given-sum-condition-解题思路分析/
Categories: leetcode
kwantong: