满足条件的子序列数目 图解题解

这道题到底在问什么

输入

nums=[3,5,6,7], target=9

输出

4

输入

nums=[3,3,6,8], target=10

输出

6

最优解：一步一步想明白

1. 3记住「排序 → 和 ≤ target 就固定最小、中间自由选 2^(r−l) 个、l 右移;和太大就 r 左移」,下面每帧都在套它。
2. 4第一步排序。原数组 [7, 3, 2, 6, 4, 3] 排好序变成 [2, 3, 3, 4, 6, 7]。因为子序列的最小值、最大值只看「选了哪些数」、跟原顺序无关,排序完全不影响答案,反而让双指针能从两端对撞。
3. 5左指针 l=0(最小值 2)、右指针 r=5(最大值 7)。最小加最大 = 2+7 = 9,不超过 target 9,说明只要把最小值钉在 2、最大值不超过 7,这一批子序列都合法。
4. 6关键一步,把计数讲透。最小值钉死在下标 0 的 2(绿色),它一定要选;剩下下标 1 到 5 这 5 个数(灰色),每一个都可以选或不选,互不影响,所以一共 2 的 5 次方 = 32 种取法。每一种取法都是一个合法子序列:最小值就是 2、最大值最多到 7,和不超过 9。一次把这 32 个全部计入 ans。
5. 7以下标 0 这个数作为「被选中的最左元素」的那一批已经数完,左指针右移到下标 1;换成更大的数当最左元素,继续考察。
6. 8左指针 l=1(当前最小值 3)、右指针 r=5(最大值 7)。最小加最大 = 10,已经超过 target 9;连当前范围里最小的 3 配上 7 都超标,说明在「最左元素从下标 1 起」这段还没统计的范围里,7 当最大值已经配不出新的合法子序列了(7 跟更小元素的组合早在前面批次算过)。于是右指针左移、换更小的最大值。
7. 9把最大值换小一点:右指针左移一格到 4(值 6),再看新的最小加最大能不能落进 target 以内。
8. 10左指针 l=1(最小值 3)、右指针 r=4(最大值 6)。最小加最大 = 3+6 = 9,不超过 target 9,说明只要把最小值钉在 3、最大值不超过 6,这一批子序列都合法。
9. 11同样地,最小值固定为 3,中间 3 个数自由选,2 的 3 次方 = 8 个合法子序列,ans 累加到 40。
10. 12以下标 1 这个数作为「被选中的最左元素」的那一批已经数完,左指针右移到下标 2;这里的值和上一个一样,但它代表的是另一批、不含下标 1 那个数的子序列,继续考察。
11. 13左指针 l=2(最小值 3)、右指针 r=4(最大值 6)。最小加最大 = 3+6 = 9,不超过 target 9,说明只要把最小值钉在 3、最大值不超过 6,这一批子序列都合法。
12. 14同样地,最小值固定为 3,中间 2 个数自由选,2 的 2 次方 = 4 个合法子序列,ans 累加到 44。
13. 15以下标 2 这个数作为「被选中的最左元素」的那一批已经数完,左指针右移到下标 3;换成更大的数当最左元素,继续考察。
14. 16左指针 l=3(当前最小值 4)、右指针 r=4(最大值 6)。最小加最大 = 10,已经超过 target 9;连当前范围里最小的 4 配上 6 都超标,说明在「最左元素从下标 3 起」这段还没统计的范围里,6 当最大值已经配不出新的合法子序列了(6 跟更小元素的组合早在前面批次算过)。于是右指针左移、换更小的最大值。
15. 17把最大值换小一点:右指针左移一格到 3(值 4),再看新的最小加最大能不能落进 target 以内。
16. 18左指针 l=3(最小值 4)、右指针 r=3(最大值 4)。最小加最大 = 4+4 = 8,不超过 target 9,说明只要把最小值钉在 4、最大值不超过 4,这一批子序列都合法。
17. 19同样地,最小值固定为 4,中间 0 个数自由选,2 的 0 次方 = 1 个合法子序列,ans 累加到 45。
18. 20左指针 l=4 已经越过右指针 r=3,所有可能的最左元素都考察完了,扫描结束,最终 ans = 45。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10**9 + 7
        nums.sort()
        pow2 = [1] * (len(nums) + 1)
        for i in range(1, len(pow2)):
            pow2[i] = pow2[i-1] * 2 % MOD
        l, r = 0, len(nums) - 1
        ans = 0
        while l <= r:
            if nums[l] + nums[r] <= target:
                ans = (ans + pow2[r-l]) % MOD
                l += 1
            else:
                r -= 1
        return ans

#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        const int MOD = 1000000007;
        sort(nums.begin(), nums.end());
        vector<int> pow2(nums.size() + 1, 1);
        for (int i = 1; i < (int)pow2.size(); ++i) pow2[i] = pow2[i-1] * 2LL % MOD;
        int l = 0, r = nums.size() - 1, ans = 0;
        while (l <= r) {
            if (nums[l] + nums[r] <= target) { ans = (ans + pow2[r-l]) % MOD; l++; }
            else r--;
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int numSubseq(int[] nums, int target) {
        int MOD = 1_000_000_007;
        Arrays.sort(nums);
        int[] pow2 = new int[nums.length + 1];
        pow2[0] = 1;
        for (int i = 1; i < pow2.length; i++) pow2[i] = (int)((long)pow2[i - 1] * 2 % MOD);
        int l = 0, r = nums.length - 1, ans = 0;
        while (l <= r) {
            if (nums[l] + nums[r] <= target) { ans = (ans + pow2[r - l]) % MOD; l++; }
            else r--;
        }
        return ans;
    }
}

复杂度

面试官可能追问