1. 题目拆解：一双指针到底在数什么

先把这个题目翻译成人话。给定一个整数数组nums和一个目标值target，要求从数组里找出所有非空子序列，并且子序列里的最大值和最小值之和不超过target，问这样的子序列一共有多少个，答案对10^9 + 7取模。

注意这里说的是“子序列”，不是“子数组”。子序列不要求元素在原数组里连续，只要保持相对顺序就行。很多人在这一步就开始慌，觉得子序列问题都得往动态规划上想。其实这道题的关键恰恰在于：题目里只关心最大值和最小值，跟元素之间的相对顺序没有关系。

为什么这么说？因为只要一个子序列的最大值max和最小值min满足min + max <= target，这个子序列里的其他元素取谁都无所谓。它们既不会让最大值变得更大，也不会让最小值变得更小，所以对“是否满足条件”这件事毫无影响。

举个最直白的例子，nums = [3, 5, 6, 7]，target = 9。子序列[3, 5]最小3最大5，8 <= 9，满足条件。子序列[3, 6]也一样满足。而[5, 6]最小5最大6，11 > 9，不满足。可以看到，只要锁定一对“最小值和最大值”，剩下的元素加不加进来，都不改变这一对的合法性。

于是问题一下就变了：与其枚举所有子序列，不如先去枚举“最小值和最大值”这一对。只要能快速统计出“以某个元素为最小值、另一个元素为最大值时，中间可以任意挑选多少个元素”，再用组合数算出来，这道题就解完了。而“枚举一对元素”这件事，正是双指针最擅长干的活。

还有一个非常容易踩的坑，就是子序列的数量可能大得离谱。比如nums有10^5个元素，理论上的子序列总数是2^10^5量级，直接枚举等于自杀。所以必须找到一个公式化的计数方法，一次性统计一大批子序列，这也是排序加双指针思路的真正意义所在。

2. 为什么可以排序：顺序不是这道题的命门

很多第一次做这道题的人会问：题目说子序列要保持相对顺序，我先排序，这不是把顺序打乱了吗？答案还能对吗？

答案是：对原数组排序完全不影响最终答案。原因前面已经铺垫了一半：判断条件只跟子序列里的最大值和最小值有关，其他元素无论怎么排列，都不改变这个子序列的最大值和最小值。既然每个子序列对应到“最大值、最小值”这一对上是唯一的，那排序后重新数出来的子序列数量，和原数组数出来的数量必然一致。

这个性质可以通过一个简单的映射来理解。原数组nums里任意一个满足条件的子序列，排序之后就是把它的元素排成非递减顺序。排序后的子序列，第一个元素就是最小值，最后一个元素就是最大值。而原数组里任何一个子序列，在排序后都会变成一个新的“有序子序列”，但最大最小值没变。反过来，排序后数组里的任何一个有序子序列，也能对应回原数组里一个同样满足条件的子序列（把那些元素按下标取出来而已）。

所以排序这一步不是“作弊”，而是一次不改变答案的预处理。它换来的是什么呢？是数组变成有序之后，**“最小值所在位置一定在最大值所在位置的左边”**这一条铁律。有了这个铁律，双指针才能成立。

还有一个容易忽略的细节：nums里可能有重复元素。排序之后重复元素会靠在一起，但这不影响计数逻辑，因为我们是按下标来区分元素的。即使两个元素值相同，它们在数组里的位置不同，就是两个不同的元素，这符合题目“子序列按下标选取”的语义。

到这里思路基本定型了：先对数组升序排序，然后固定一个左边界（最小值），右边界（最大值）从右侧不断收缩，直到找到最后一个满足nums[left] + nums[right] <= target的位置。那么这个区间里的所有“以left为最小值的子序列”，数量可以直接用2^(right-left)算出来，累加到答案里。

有人会问为什么是2^(right-left)而不是2^(right-left+1)，后面讲实现的时候我会好好掰扯一下。这里先记住一个核心观点：双指针移动的是“合法区间”的边界，而不是在暴力枚举子序列。每移动一次左指针，就能数出一整批子序列，这正是这道题效率高的原因。

3. 双指针滑窗实现：从公式推导到完整代码

3.1 一个直观的计数思路：固定最小值

先说计数公式的来源。假设排序后的数组是a[0] <= a[1] <= ... <= a[n-1]，我固定a[i]作为子序列的最小值，然后找到一个最大的下标j，使得a[i] + a[j] <= target。

根据有序性，a[i+1]到a[j]之间的所有元素，任意取多少个都可以和a[i]组成合法子序列。为什么？因为这些元素的值都小于等于a[j]，它们和a[i]相加也不会超过target，而且a[i]始终是最小值。所以对于固定的i，可选元素的个数是j - i，每个元素“选或者不选”都是自由的，于是合法子序列数是2^(j-i)。

注意这里为什么不包含a[i]自己单独一个元素的情况。实际上a[i]单独构成一个长度为1的子序列时，最大值等于最小值等于a[i]，条件是2 * a[i] <= target。这个情况其实已经被包含在j >= i的情况里了：如果j == i，说明只有a[i]一个元素能选，可选元素个数0，2^0 = 1，正好对应单元素子序列。所以只要保证初始时j不小于i，那个长度为1的子序列就被天然算进去了。

接下来就是双指针的移动逻辑。按这个思路，我有两个方向可以枚举：

• 方向A：从左到右枚举i，每次让j从右往左收缩到合法位置，统计2^(j-i)，然后i++。
• 方向B：从右到左枚举j，每次让i从左往右扩展到合法位置，统计2^(j-i)，然后j--。

两种写法本质一样，区别在于循环的落脚点。我更推荐方向A，因为它更贴近“固定左端点、扩展右端点”的直觉。

3.2 指针怎么移动：配合单调性减少重复计算

如果直接对每个i都重新从数组末尾开始找j，复杂度就是O(n^2)，跟暴力没太大区别。双指针的精髓在于利用有序性，让左右指针都只往一个方向移动，总移动次数是O(n)。

具体做法是：左指针i从0开始，右指针j从n-1开始。当i向右移动时，a[i]变大，那么合法的j只可能向左移动，不可能向右移动。这是一条至关重要的单调性结论。因为a[i]变大了，原来满足a[i] + a[j] <= target的那些j，现在必须变得更小才能保持不等式成立。所以右指针永远只往左走，不需要回退。

伪代码逻辑如下：

sort(nums) n = len(nums) ans = 0 j = n - 1 for i in range(n): while j >= i and nums[i] + nums[j] > target: j -= 1 if j < i: break ans += pow2[j - i] return ans % MOD

当j < i时，说明连nums[i]自己作为最小值都跟一个同样大小的元素配对不了，更不用说更大的元素了，那么后面的i也不可能再找到合法区间，直接break掉。

这里幂运算2^(j-i)如果每次都快速幂，复杂度是O(n log n)，单独看也还行。但既然题目对取模有要求，而且n最大到10^5，更高效的做法是提前预处理一个pow2数组，把2^0到2^n都算好，每个位置O(1)查表。

pow2 = [1] * (n + 1) for i in range(1, n + 1): pow2[i] = (pow2[i - 1] * 2) % MOD

3.3 完整代码：两个语言的参考实现

先给Python版本，最接近伪代码，适合用来理解逻辑：

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

再给一个Java版本，因为在力扣环境里Java的int类型很容易溢出，处理取模时要格外小心：

class Solution { public int numSubseq(int[] nums, int target) { final int MOD = 1_000_000_007; Arrays.sort(nums); int n = nums.length; int[] pow2 = new int[n + 1]; pow2[0] = 1; for (int i = 1; i <= n; i++) { pow2[i] = (int)((long) pow2[i - 1] * 2 % MOD); } long ans = 0; int j = n - 1; for (int i = 0; i < n; i++) { while (j >= i && nums[i] + nums[j] > target) { j--; } if (j < i) { break; } ans = (ans + pow2[j - i]) % MOD; } return (int) ans; } }

核心就这几行，没有复杂状态转移，也没有递归回溯。我见过不少人在while条件里写nums[i] + nums[j] > target时忘了加j >= i的前置判断，结果数组越界。这个问题在下一章专门讲。

3.4 取模运算的正确姿势

先聊一个实战中非常容易翻车的点：幂运算结果和累加结果都可能超出语言默认整数类型的范围。

Python里整数是任意精度的，不担心溢出，但Java和C++里int只有32位。2^30约等于10^9，2^31就超过int上限了，而10^9 + 7恰好比2^30大一点。所以计算pow2[i] = pow2[i - 1] * 2 % MOD时，中间结果pow2[i - 1] * 2最多是2 * (MOD - 1)，也就是大约2 * 10^9，已经超过int的正数上限2147483647很近了，一不小心就溢出。

Java里我最常写的模式就是(int)((long) pow2[i - 1] * 2 % MOD)，先把pow2[i - 1]转成long再乘，这样中间结果最多2e9，远小于long上限，最后取模后转回int。累加ans时也是一样的套路，ans用long，每次加完立即取模。

C++里可以用long long，只要你记得1LL *这种写法，别让两个int直接乘。

4. 边界细节与复杂度：能不能一次写对

4.1 一个必须小心的高频坑：while里的指针越界

前面提到while (j >= i && ...)这个判断顺序很关键。如果你把条件反过来写，或者忘了j >= i，在极端情况下会发生什么？

看这个例子：nums = [1, 1, 1, 1]，target = 1。排序后nums[0] + nums[3] = 2 > 1，右指针一路左移。如果没有j >= i的保护，当j移动到-1时再去访问nums[j]，直接越界报错。Java会抛ArrayIndexOutOfBoundsException，C++是未定义行为，可能得到垃圾值，导致答案错误。

还有一类情况是j提前收缩到i - 1，这时当前i已经没有任何合法子序列了。按逻辑应该break掉整个循环，因为后续的i只会更大，更不可能合法。如果不break，j - i会变成负数，pow2数组访问越界。

边界速查表：

4.2 复杂度分析：为什么这是“最优解”

排序是O(n log n)，双指针部分每个指针最多移动n次，总移动次数O(n)，再加上预处理pow2的O(n)，整体时间复杂度O(n log n)。空间复杂度O(n)，主要是排序和pow2数组，Python里排序本身需要O(n)额外空间，Java的Arrays.sort对基本类型是双轴快排，O(log n)栈空间，这里统一按O(n)算就行。

对于子序列计数类问题，O(n log n)基本就是天花板了。因为你要么排序预处理，要么用哈希表维护某种频次，但哈希表无法直接解决“最大值加最小值”这种二元约束。O(n log n)已经能轻松应对10^5量级的输入，没必要再去追求更极限的优化。

4.3 用一个手算例子验证逻辑

拿nums = [3, 3, 6, 8]，target = 10来走一遍：

排序后不变。初始化i = 0，j = 3。

• i = 0：nums[0] + nums[3] = 11 > 10，j左移到2。此时3 + 6 = 9 <= 10，合法区间长度j - i = 2，贡献2^2 = 4个子序列。这四个分别是[3]、[3, 6]、[3, 3]（这里两个3位置不同所以算两个不同子序列）、[3, 3, 6]。等等，我数一下，固定i=0（第一个3）作为最小值，可选元素是第二个3和6，四个组合分别是：只选自己、选第二个3、选6、选第二个3和6。确实四种。
• i = 1（第二个3）：右指针j保持2。nums[1] + nums[2] = 9 <= 10，贡献2^(2 - 1) = 2。这两个是[3]和[3, 6]，这里的最小值是第二个3，跟上一轮虽然值相同，但下标不同，所以子序列不同。
• i = 2（元素6）：nums[2] + nums[2] = 12 > 10，j左移到1。但此时j < i，直接break。

答案4 + 2 = 6。可以手动枚举验证：合法的非空子序列是[3a]、[3b]、[6]、[3a,3b]、[3a,6]、[3b,6]，一共6个。[3a,3b,6]最小3最大6，但注意[3a,3b,6]其实也被包含在i=0时的2^2里了，我上面漏写了，实际上应该是[3a]、[3a,3b]、[3a,6]、[3a,3b,6]，加上i=1的[3b]、[3b,6]，总共6个。完美对应。

这个小例子能看出一个关键点：值为3的两个不同位置元素，被当成两个不同的“最小值”来计数，所以重复值不会造成计数缺失，也不会重复计算同一个子序列。因为每个子序列对应唯一的最小值下标，即使值相同，下标不同，子序列就不同。

5. 变体与进阶：一法通，百法通

5.1 从“最小+最大”到“和为target”的配对题

双指针在配对类问题里非常常见。比如经典的“排序数组中和为target的两个数”问题：左右指针分别指向首尾，如果nums[left] + nums[right] < target，说明和太小，左指针右移；如果大于target，右指针左移；相等就记录答案，然后两边同时收缩。

这类问题的本质是：有序数组上，左指针和右指针各往一个方向移动，整个搜索空间被压缩成一条单调的扫描线。和本题的区别在于，本题需要“计数”而非“配对”，而且每个左指针可以匹配很长一段右区间。

5.2 差为target的配对怎么处理

如果把题目改成“找两个数，差的绝对值等于target”，双指针当然也能做，但策略变了。排序后，让左指针从0开始，右指针也从0开始，二者都向右移动。当nums[right] - nums[left] < target时，右指针前进；等于target时记录答案；大于target时左指针前进。这种写法叫同向双指针，在“差为target”和“滑动窗口求区间和”问题里非常常见。

同向双指针和本题的相向双指针差别在哪？相向双指针适用于“两个元素之和”这种约束，因为两个元素一个偏大一个偏小，从两端向中间收缩最自然。同向双指针适用于“区间性质”这种约束，两个指针都从左往右走，维护一个窗口。

5.3 还是子序列，但约束改成“最大-最小 <= k”

如果题目条件改成最大值减最小值不超过某个数，思路依然可以沿用排序加双指针，只是不等式从加法变成减法。排序后，固定左端点i，找最大的j满足nums[j] - nums[i] <= k，贡献2^(j-i)。代码几乎一模一样，改一下while条件里的大于号方向就行。

这说明一个非常重要的迁移能力：只要子序列的合法性只取决于最大最小值，并且两个端点之间存在某种单调性，排序加双指针就是首选解法。至于约束是加法、减法、乘积还是对数，只要不等式在有序数组里保持单调，套路不变。

5.4 殊途同归：二分查找版本

双指针的另一个替代写法是二分查找。对每个固定的i，用二分在[i, n-1]范围内找最大的j满足nums[j] <= target - nums[i]，然后贡献2^(j-i)。每次二分O(log n)，总复杂度O(n log n)，和双指针复杂度相同。

那为什么我更推荐双指针？因为双指针的均摊复杂度是O(n)，二分是O(n log n)，在10^5规模下差距不明显，但双指针代码更短，也不容易在二分边界上翻车。而且双指针的“相向收缩”过程在理解上比二分嵌套更直观，能顺便训练对单调性的敏感度。

6. 踩坑实录与调试技巧

6.1 四个真实高频错误

这个题我在不同场景里见过不少人翻车，集中在这几类：

第一，while条件漏掉j >= i，数组越界。这个前面已经重点讲过了，最典型的症状是本地测试小用例没事，一提交就报错，或者在某些极端输入上随机崩溃。

第二，忘记取模或者取模时机不对。有些人在pow2预处理时取模了，但累加答案时想着“最后再取一次模”，结果中间ans已经超出long上限。在Java里long虽然很大，但2^10^5的情况你不可能真的累加那么多次，因为每次都取模才是正解。如果最后取模，ans早就爆了。

第三，把子序列和子数组搞混。如果按子数组来做，用滑动窗口维护区间内最大最小值，复杂度会更高，而且统计公式完全不对。滑动窗口统计的是连续区间数量，子序列是组合选择，两者差着指数级。

第四，排序后直接用nums[i] + nums[j]时溢出。虽然单个元素的范围通常不超过10^9，但两个int相加可能到2 * 10^9，超过int正上限。在判断条件里，建议写成nums[i] > target - nums[j]来避免加法溢出，或者直接把数组转成long类型再操作。

6.2 调试技巧：小数据手算 + 对拍验证

我调试这类计数题有个习惯：先用n <= 10的随机小数组，暴力枚举所有子序列（用位运算枚举子集），然后把双指针代码的结果跟暴力结果对拍。只要对拍几百组随机数据全部一致，正确性基本就有保障了。

一个Python暴力对拍的核心代码长这样：

from itertools import combinations def brute(nums, target): n = len(nums) ans = 0 for r in range(1, n + 1): for comb in combinations(range(n), r): vals = [nums[i] for i in comb] if min(vals) + max(vals) <= target: ans += 1 return ans % (10**9 + 7)

然后随机生成数组，跑brute和numSubseq对比。这个过程能抓出绝大多数逻辑错误，尤其是重复计数和漏计数问题。

6.3 关于模运算的一个反直觉细节

10^9 + 7是质数，所以很多时候可以直接用费马小定理做模逆元。但本题的幂是2的整数次幂，不需要逆元，直接预处理就行。

有个反直觉的点是：pow2[i]预处理到n就够了，不需要到2*n或者更大。因为j - i的最大值就是n - 1，发生在i = 0且所有数都合法时。所以数组长度设为n + 1就完全覆盖。

另一个细节是ans的累加。因为每次只加pow2[j-i]，这个值已经模过MOD，所以ans + pow2[...]不会超过2 * MOD，理论上用if (ans >= MOD) ans -= MOD这种常数级优化也行。但实际上取模运算的耗时在现代CPU上几乎可以忽略，考试和面试中没必要做这种微优化，可读性优先。

7. 从这道题延伸出去：双指针专题怎么刷

双指针算法说来神秘，其实就三种形态：相向双指针、同向双指针、快慢指针。本题是相向双指针的经典代表。

相向双指针最适合处理“有序数组中两个元素满足某种关系”的题目，比如两数之和、三数之和、盛最多水的容器、接雨水。这类题的核心是：当左指针右移让某个值变大时，右指针一定只能左移，反之亦然，整个搜索过程不会走回头路。

同向双指针适合处理“连续子数组/子串满足某种性质”的题目，比如无重复字符的最长子串、长度最小的子数组、水果成篮。这类题维护一个窗口，窗口右边界扩张，左边界收缩，每次窗口变化时更新答案。

快慢指针适合处理链表环、链表中间节点、原地去重这类问题。

如果你想把双指针吃透，我的建议是刷题时别急着看题解，先问自己三个问题：题目是否有序？两个指针是否只会朝一个方向移动？每次移动能一次性排除多少候选答案？这三个问题想明白了，双指针基本都是水到渠成。

回到“满足条件的子序列数目”这道题，它最漂亮的地方在于：把一个看起来需要指数级枚举的子序列计数问题，通过排序把维度压缩到最小值和最大值两个点，再通过双指针把配对过程优化到线性扫描。整个过程没有花哨的DP，没有复杂的组合数学，只有对单调性的深刻理解。

我个人做完这道题最大的体会是：子序列计数问题不一定非要动态规划。当条件只依赖极值时，先排序往往能化腐朽为神奇。以后再遇到“子序列 + 最大最小 + 某种约束”的题目，我第一个想到的就是排序加双指针加组合数，而不是一头扎进状态转移方程里。

最后再分享一个很多人不知道的小技巧：如果你担心双指针的while条件写错，可以在纸上把“左指针固定时，右指针能取到的最远位置”画成一条阶梯线。左指针每右移一次，阶梯线只可能下降，不可能上升。理解了这条阶梯线，双指针的边界处理基本不会再出错。这个技巧，我后来刷三数之和、四数之和时一直在用，屡试不爽。