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

2026-05-18 HGNULB 约 10 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

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

题意分析

给定数组 nums 和整数 target，统计有多少个非空子序列满足「其最小元素与最大元素之和不超过 target」，答案对 $10^9 + 7$ 取模。

关键要看穿一层伪装：题目说的是子序列（要求保持原相对顺序），但判定条件只用到这个子序列的最小值与最大值，而最小值最大值与元素的排列顺序无关。也就是说，两个由相同元素集合构成的子序列，要么都合法要么都不合法，且不同的下标集合对应不同的子序列。于是可以自由地把 nums 排序——排序改变的只是下标与元素的对应关系，不改变「合法下标集合的数量」。这一步是全题的题眼。

数据范围 $n \le 10^5$，而子序列共有 $2^n - 1$ 个，说明绝不能逐个枚举，必须批量计数。同时 $n \le 10^5$ 也允许 $O(n \log n)$ 的排序。$nums[i]$ 与 target 都在 $10^6$ 量级，两数相加不会溢出 int。

边界要盯住三处：单元素子序列的最小值和最大值是同一个数，条件退化为 $2 \times nums[i] \le target$，这类子序列必须被计入；答案要取模，而幂 $2^{n-1}$ 远超 int，预处理时就得取模；数组中最小的两个元素之和都大于 target 时答案为 $0$。

解法：排序 + 双指针 + 预处理幂次

核心思路

暴力枚举全部 $2^n$ 个子序列显然不可行。稍进一步的想法是枚举「最小值」和「最大值」这一对元素，但那是 $O(n^2)$ 对，$n = 10^5$ 时仍是 $10^{10}$。

排序之后，问题的结构一下子清晰了：一个子序列的最小值和最大值，就是它在排序数组中下标最小和下标最大的那两个元素。于是只枚举最小元素的下标 left，问最大元素的下标最远能到哪里。由于数组已升序，nums[left] + nums[r] 关于 $r$ 单调不减，所以存在一个分界点 right，使得 $r \le right$ 时合法、$r > right$ 时非法。

固定了 left 作为最小元素、允许的最大下标是 right 之后，中间那些下标 left+1 .. right 共 right - left 个元素每个都可以自由选或不选：选任意子集，得到的子序列最小值仍是 nums[left]（因为 left 必选且它是最小的），最大值不会超过 nums[right]，条件依然满足。所以这一档的贡献恰好是 $2^{right - left}$。注意 left 本身必须被选中，否则最小值就不是它了，这保证了不同 left 之间统计的子序列互不重复——每个合法子序列恰好被它自己的最小元素统计一次，这就是不重不漏的依据。

剩下的问题是快速求出每个 left 对应的 right。可以对每个 left 二分，总代价 $O(n \log n)$；但注意到 nums[left] 随 left 增大而不减，所以合法的 right 只会不增，于是可以用双指针：left 从左往右、right 从右往左，各自单向移动，总代价 $O(n)$。

循环的不变量是：所有以下标 $< left$ 的元素为最小值的合法子序列都已统计完毕；当前 [left, right] 是尚未处理的候选区间，且 nums[right] 是「配 nums[left] 时可能合法」的最大候选。每轮判断 nums[left] + nums[right] <= target：成立则说明以 left 为最小值时上界正是 right，累加 $2^{right-left}$ 并把 left 右移；不成立则 nums[right] 太大，它配不上当前这个（也是剩余中最小的）left，那它配任何更大的 left 更不可能，可以永久丢弃，right 左移。

$2^{right-left}$ 的指数最大是 $n - 1$，每次现算快速幂是 $O(\log n)$，不如预处理 pow2[0..n-1] 数组，一次线性递推全部取模算好，查询 $O(1)$。

解题步骤

先对 nums 升序排序。合法性只由最小值与最大值决定，与顺序无关，排序把「找子序列的极值」变成了「看区间的两端」，这是后续所有推理的前提。

预处理 pow2 数组，pow2[0] = 1，pow2[i] = pow2[i-1] * 2 % mod。递推而非快速幂，是因为要用到的指数覆盖 $0$ 到 $n-1$ 的连续区间，线性递推总代价 $O(n)$ 且常数极小。Java 里必须写成 (long) pow2[i-1] * 2 % mod，先升 long 再乘，否则接近 $10^9$ 的值乘 $2$ 会溢出 int。

双指针初始化 left = 0、right = n - 1，answer = 0。两端出发是因为一端在找最小值、另一端在收缩最大值的上界。

循环条件用 left <= right，等号必须保留。left == right 时对应的是「只含这一个元素」的子序列，若条件满足应贡献 $2^0 = 1$；写成 < 会漏掉全部单元素子序列。

若 nums[left] + nums[right] <= target，累加 pow2[right - left] 并 left++。此时 right 就是配 left 的最远上界，中间 right - left 个元素自由取舍；累加后 left 这个最小值已经被穷尽，推进到下一个。

否则 right--。当前 nums[left] 是剩余元素中最小的，它都配不上 nums[right]，那么任何更大的最小值更配不上，nums[right] 从此不可能作为任何合法子序列的最大值，安全丢弃。注意这一支不能累加任何东西。

每次累加后取模，answer + pow2[...] 最大约 $2 \times 10^9$，Java 中 int 会溢出，所以取模要紧跟加法（本题两数相加恰好卡在 int 边缘，写成 (answer + pow2[...]) % mod 时中间值 $2 \times 10^9$ 已超 int 上限，稳妥做法是保证 answer 与 pow2 都已在 $[0, mod)$ 内，此时和小于 $2^{31}$，恰好安全）。

返回 answer。

以 nums = [3, 5, 6, 7]、target = 9 走一遍：

排序后仍是 [3, 5, 6, 7]。预处理 pow2 = [1, 2, 4, 8]。初始 left = 0、right = 3、answer = 0。
第一轮：$3 + 7 = 10 > 9$，不合法，right-- 变成 $2$。丢掉 $7$：既然最小的 $3$ 都配不上它，它永远不能当最大值。
第二轮：$3 + 6 = 9 \le 9$，合法。贡献 pow2[2 - 0] = 4，answer = 4。这 4 个子序列是：以 $3$ 为最小、$6$ 为上界，中间可选的是 $5$ 和 $6$ 两个元素的任意子集——即 ${3}, {3,5}, {3,6}, {3,5,6}$。left++ 变成 $1$。
第三轮：$5 + 6 = 11 > 9$，right-- 变成 $1$。
第四轮：left == right == 1，$5 + 5 = 10 > 9$，right-- 变成 $0$，循环因 left > right 退出。
返回 $4$。

验证一下手工枚举：合法子序列需最小加最大不超过 $9$，${3}$（$3+3=6$）、${3,5}$（$8$）、${3,6}$（$9$）、${3,5,6}$（$9$）合法；${5}$ 是 $10$、${6}$ 是 $12$ 均不合法。共 $4$ 个，吻合。注意这里第二轮一次性用 $2^2$ 覆盖了 $4$ 个子序列，正是「中间元素自由选取」的批量计数在起作用。

代码实现

class Solution {
    public int numSubseq(int[] nums, int target) {
        int mod = 1000000007;
        Arrays.sort(nums);

        int n = nums.length;
        int[] pow2 = new int[n];
        pow2[0] = 1;
        for (int i = 1; i < n; i++) {
            pow2[i] = (int) ((long) pow2[i - 1] * 2 % mod);
        }

        int left = 0;
        int right = n - 1;
        int answer = 0;
        while (left <= right) {
            if (nums[left] + nums[right] <= target) {
                answer = (answer + pow2[right - left]) % mod;
                left++;
            } else {
                right--;
            }
        }

        return answer;
    }
}

func numSubseq(nums []int, target int) int {
    const mod = 1000000007
    sort.Ints(nums)

    n := len(nums)
    pow2 := make([]int, n)
    pow2[0] = 1
    for i := 1; i < n; i++ {
        pow2[i] = pow2[i-1] * 2 % mod
    }

    left := 0
    right := n - 1
    answer := 0
    for left <= right {
        if nums[left]+nums[right] <= target {
            answer = (answer + pow2[right-left]) % mod
            left++
        } else {
            right--
        }
    }

    return answer
}

复杂度分析

时间复杂度：$O(n \log n)$。排序占 $O(n \log n)$ 且是全程的瓶颈；预处理幂次是一趟 $O(n)$；双指针阶段 left 只增、right 只减，两者相向而行，总移动次数不超过 $n$，所以是 $O(n)$。若输入已有序则整体降为 $O(n)$。

空间复杂度：$O(n)$。主要是长度为 $n$ 的 pow2 数组；此外 Java 对 int[] 用双轴快排是原地的，额外栈空间 $O(\log n)$，Go 的 sort.Ints 同理。若改用快速幂现算可把空间降到 $O(1)$，但时间要多一个 $\log$ 因子。

关键点总结

判定条件只依赖集合的某些聚合量（最值、和、计数）而与顺序无关时，「子序列」和「子集」是等价的，可以放心排序。识别这一点是把 $O(2^n)$ 变成多项式的第一步。

计数问题要设计「不重不漏」的归属规则。本题把每个合法子序列归属给它的最小元素，于是枚举最小元素就能穷尽所有情况且互不相交；这种「按某个唯一代表元分类」的思路在组合计数里非常通用。

固定一端后，若中间元素的取舍完全自由，就能用 $2^m$ 一次性代替 $2^m$ 次枚举。看到「中间随便选」立刻想到幂次贡献。

双指针能替代逐个二分的前提是「两个指针的目标位置都单调」。本题因为排序后 nums[left] 不减、所以对应的 right 不增，相向移动才成立；若单调性不成立就只能老老实实二分。

面试视角：面试官会先确认你是否敢排序——要主动说明「条件只看最值，与顺序无关，所以子序列计数等价于子集计数」。接着会问「为什么不会重复计数」，答「每个子序列由它的最小元素唯一归属」。最后会问溢出与取模：预处理时乘 $2$ 要先转 long，累加时保证两个加数都已归约到 $[0, mod)$。这三问答完基本满分。

易错点总结

循环条件写成 left < right：nums = [5]、target = 10 时循环一次都不进，返回 $0$，而 ${5}$ 满足 $5 + 5 \le 10$，正确答案是 $1$；所有只剩单元素的档位都会被漏掉。

不合法分支也累加贡献：把 right-- 那一支也写上 answer += pow2[right-left]，nums = [3, 5, 6, 7]、target = 9 会返回大于 $4$ 的值。

合法时移动 right 而非 left：nums = [3, 5, 6, 7]、target = 9 第二轮合法后把 right 减到 $1$，后续再也统计不到以 $3$ 为最小值之外的情况，且同一档可能被重复累加，返回值错误。

贡献写成 pow2[right - left + 1]：nums = [3, 5, 6, 7]、target = 9 时第二轮贡献 $8$ 而非 $4$，返回 $8$，把 left 也当成了可选元素，而 left 必须被选中。

预处理时不升 long 直接乘：pow2[i-1] 接近 $10^9$ 时乘 $2$ 溢出 int 变负数，后续所有幂次全错，答案变成负数或乱码。

忘记排序直接双指针：nums = [6, 3, 7, 5]、target = 9 时 nums[0] + nums[3] = 11 > 9 先减 right，整个流程建立在错误的单调性上，返回值与正确答案 $4$ 不符。

累加时先加后取模但 answer 未归约：若某处漏写 % mod 让 answer 超过 $10^9$，再加一个接近 $10^9$ 的幂次就会突破 int 上限变负，最终返回负数。

用 Math.pow(2, right-left) 代替预处理：返回 double，指数到 $53$ 以上就丢精度，n = 10^5 时结果完全错误，且没有取模。

把「子序列」理解成「连续子数组」：nums = [3, 5, 6, 7]、target = 9 只统计连续段会得到 ${3}, {3,5}, {3,5,6}$ 三个，漏掉不连续的 ${3,6}$，返回 $3$。

pow2 数组只开到 n - 1 却访问 pow2[n]：把贡献误写成 pow2[right - left + 1] 时，left = 0、right = n - 1 会访问下标 $n$ 直接越界。

相似题目

题目	难度	考察点
167. 两数之和 II - 输入有序数组	中等	相向双指针的最简形态，求的是恰好等于目标的唯一一对，不涉及批量计数
259. 较小的三数之和	中等	同为排序后双指针批量计数，一次合法直接累加 `right - left` 对而非幂次
611. 有效三角形的个数	中等	排序后固定最大边再双指针，同样一次累加一段区间的对数
15. 三数之和	中等	排序加双指针枚举组合，重点在去重而非计数
713. 乘积小于 K 的子数组	中等	同向滑动窗口批量计数，对象是连续子数组，不能排序
78. 子集	中等	需要真正枚举 $2^n$ 个子集，本题的 $2^m$ 贡献正是它的计数版本
11. 盛最多水的容器	中等	相向双指针求最优而非计数，收缩依据是「短板永远不可能更优」
940. 不同的子序列 II	困难	同为子序列计数取模，但要求去重且必须保持顺序，需按结尾字符做 DP