Leetcode: 1498. 满足条件的子序列数目

本文主要是介绍Leetcode: 1498. 满足条件的子序列数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给你一个整数数组 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

分析

首先这个题目情景会让人想到回溯法，但是回溯法的算法复杂度过大，因为它实际是搜索了所有的情况再进行判断。

因为对一个子序列来说，我们只关心它的最小值和最大值，所以原序列中元素的顺序可以任意改变，当然也可以排序。

对于序列 [1, 2, 3]，它的子序列是 {[1], [1, 2], [1, 3], [1, 2, 3], [2], [2, 3], [3]}, 可以拆成 7 = $2^2 + 2^1 + 2^0$ ，分别对应 {[1], [1, 2], [1, 3], [1, 2, 3]}， {[2], [2, 3]}，{[3]}。

设 [left, right] 表示一个子序列，只要 nums[left] + nums[right] <= target, 那么它产生的包含 nums[left] 的序列都是合法的，有 $2^{right - left}$ 个。

比如：对序列 [1, 2, 3], target = 6，nums[0] + nums[2] <= 6, 包含 nums[0] = 1 的序列有 $2^{2- 0}$ = 4 个；nums[1] + nums[2] <= 6, 包含 nums[1] = 2 的序列有 $2^{2- 1} = 2$ 个；nums[2] + nums[2] <= 6, 包含 num[2] = 3, 的序列有 $2^{2 - 2} = 1$ 个。

分析到这里，可以利用双指针来解决这个问题：

初始化 left = 0, right = nums.length -1, ans = 0
当 left <= right 时：

如果 nums[left] + nums[right] <= target:
- 给 ans 加 $2^{right - left}$
- left++
如果 nums[left] + nums[right] > target
- right--

代码

class Solution {public int numSubseq(int[] nums, int target) {Arrays.sort(nums);int mod = 1000000007;int[] pow = new int[(int) Math.pow(10, 5) + 1];pow[0] = 1;for (int i = 1; i < pow.length; i++) {pow[i] = (pow[i - 1] * 2) % mod;}int ans = 0;int left = 0, right = nums.length - 1;while (left <= right) {if (nums[left] + nums[right] <= target) {ans = (ans + pow[right - left]) % mod;left++;} else {right--;}}return ans;}
}

注意： $2^n$ 可能会很大，所以提前打表。