满足条件的子序列数目

记住「排序 → 和 ≤ target 就固定最小、中间自由选 2^(r−l) 个、l 右移;和太大就 r 左移」,下面每帧都在套它。

第一步排序。原数组 [7, 3, 2, 6, 4, 3] 排好序变成 [2, 3, 3, 4, 6, 7]。因为子序列的最小值、最大值只看「选了哪些数」、跟原顺序无关,排序完全不影响答案,反而让双指针能从两端对撞。

左指针 l=0(最小值 2)、右指针 r=5(最大值 7)。最小加最大 = 2+7 = 9,不超过 target 9,说明只要把最小值钉在 2、最大值不超过 7,这一批子序列都合法。

关键一步,把计数讲透。最小值钉死在下标 0 的 2(绿色),它一定要选;剩下下标 1 到 5 这 5 个数(灰色),每一个都可以选或不选,互不影响,所以一共 2 的 5 次方 = 32 种取法。每一种取法都是一个合法子序列:最小值就是 2、最大值最多到 7,和不超过 9。一次把这 32 个全部计入 ans。

以下标 0 这个数作为「被选中的最左元素」的那一批已经数完,左指针右移到下标 1;换成更大的数当最左元素,继续考察。

左指针 l=1(当前最小值 3)、右指针 r=5(最大值 7)。最小加最大 = 10,已经超过 target 9;连当前范围里最小的 3 配上 7 都超标,说明在「最左元素从下标 1 起」这段还没统计的范围里,7 当最大值已经配不出新的合法子序列了(7 跟更小元素的组合早在前面批次算过)。于是右指针左移、换更小的最大值。

把最大值换小一点:右指针左移一格到 4(值 6),再看新的最小加最大能不能落进 target 以内。

左指针 l=1(最小值 3)、右指针 r=4(最大值 6)。最小加最大 = 3+6 = 9,不超过 target 9,说明只要把最小值钉在 3、最大值不超过 6,这一批子序列都合法。

同样地,最小值固定为 3,中间 3 个数自由选,2 的 3 次方 = 8 个合法子序列,ans 累加到 40。

以下标 1 这个数作为「被选中的最左元素」的那一批已经数完,左指针右移到下标 2;这里的值和上一个一样,但它代表的是另一批、不含下标 1 那个数的子序列,继续考察。

左指针 l=2(最小值 3)、右指针 r=4(最大值 6)。最小加最大 = 3+6 = 9,不超过 target 9,说明只要把最小值钉在 3、最大值不超过 6,这一批子序列都合法。

同样地,最小值固定为 3,中间 2 个数自由选,2 的 2 次方 = 4 个合法子序列,ans 累加到 44。

以下标 2 这个数作为「被选中的最左元素」的那一批已经数完,左指针右移到下标 3;换成更大的数当最左元素,继续考察。

左指针 l=3(当前最小值 4)、右指针 r=4(最大值 6)。最小加最大 = 10,已经超过 target 9;连当前范围里最小的 4 配上 6 都超标,说明在「最左元素从下标 3 起」这段还没统计的范围里,6 当最大值已经配不出新的合法子序列了(6 跟更小元素的组合早在前面批次算过)。于是右指针左移、换更小的最大值。

把最大值换小一点:右指针左移一格到 3(值 4),再看新的最小加最大能不能落进 target 以内。

左指针 l=3(最小值 4)、右指针 r=3(最大值 4)。最小加最大 = 4+4 = 8,不超过 target 9,说明只要把最小值钉在 4、最大值不超过 4,这一批子序列都合法。

同样地,最小值固定为 4,中间 0 个数自由选,2 的 0 次方 = 1 个合法子序列,ans 累加到 45。

左指针 l=4 已经越过右指针 r=3,所有可能的最左元素都考察完了,扫描结束,最终 ans = 45。

边界:单元素看 2x;2·最小值仍超标则返回 0;2·最大值仍不超标则全部 2^n−1 个都合法。

认出「排序 + 对撞双指针」母题,命中后用 2^(r−l) 批量计数是本题特色。