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

约 5 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 百度
标签
数组 排序 双指针 二分查找

题目描述

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

image-20260928230354805

image-20260928230354816

题意分析

统计所有非空子序列，使所选元素的最小值与最大值之和不超过 target，答案对 10^9+7 取模。不同下标上的相等元素仍对应不同选择。

条件只与所选元素的最小值、最大值有关，与它们原来的先后顺序无关。把每个原位置的元素看成独立个体，排序只是重排这些个体：每个原下标集合仍与排序后的某个选择集合一一对应，因此计数不变。

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

核心思路

[!blue]

排序后，按“被选中元素中最左的位置”把所有非空选择分组。固定这个位置为 left，它必须被选中，且是本组最小值；其余元素只能从右侧选择。

用 right 表示当前允许考虑的最右位置。若 nums[left]+nums[right] > target，即使配上当前最小值，right 都不合法；之后 left 只会右移、最小值只会变大，所以这个 right 对后续分组也无用，可以永久左移。

当两端之和满足条件时，left+1..right 内的每个元素都不大于 nums[right]。它们各自可选或不选，任何组合与必选的 left 放在一起都合法，因此本组共有 2^(right-left) 种。right 只是上界，不要求选中；全都不选时，只保留 left 这一项，也属于非空子序列。

累加完这一组后，令 left++，再统计下一个最左位置。每个非空选择都有唯一的最左位置，所以各组互不重复，又覆盖全部可能。即使多个值相等，它们的排序位置仍不同，不需要去重。

右指针无需回退，因为最小值越大，能够搭配的最大值上界只会不变或变小。提前用递推 pow2[i] = 2×pow2[i-1] mod MOD 保存幂值，每组就能常数时间计数。

解题步骤

  1. 对数组排序，预处理 pow2[0..n-1]，其中 pow2[0] = 1。
  2. 令 left = 0、right = n-1，在 left <= right 时继续。
  3. 若两端之和过大，令 right--，排除无法作为最大值的右端。
  4. 否则累加 pow2[right-left] 并取模，再令 left++，处理下一个分组。
  5. 两指针交错后结束，返回累计结果。只有一个候选时也要检查，最小值和最大值可以都是该元素本身。

代码实现

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

import "sort"

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+1))$。排序占主导，幂值预处理和双指针扫描均为 $O(n)$。
  • 空间复杂度：$O(n)$。主要用于幂值表；排序会改变输入数组的顺序。

关键点总结

[!green]

  • 排序不改变选中元素的最小值和最大值，每个原下标集合仍有对应的选择。
  • 固定最左所选位置，既保证非空，也让每个子序列只归入一个分组。
  • 右端只是可选范围的上界，不必出现在实际子序列中。
  • 左端右移后，合法右端不会变得更靠右，因此双指针只需单向移动。

易错点总结

[!yellow]

  • 将 right 也强制选中，会漏掉最大值小于它的合法选择。
  • 对相等元素去重，会把不同下标对应的子序列合并，造成少计。
  • 使用 left < right 而不检查相等情况，会漏掉合法的单元素子序列。
  • 用 2^(right-left+1) 计数，会错误地把必选的 left 也当成可选项。
  • 用浮点幂计算大指数再取模会失去精度，应逐步倍增并取模。

相似题目

题目 难度 关联与区别
167. 两数之和 II - 输入有序数组 中等 排序后用最小值与最大值的和收缩边界，本题不只选择两端，还要统计中间元素的任选方案。
78. 子集 中等 固定最小位置后，可选中间元素各自取或不取，贡献为2的相应次幂。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/93670217
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！