MediumRating 2276
1498. Number of Subsequences That Satisfy the Given Sum Condition
arraytwo-pointersbinary-searchsorting
解題說明
Number of Subsequences That Satisfy the Given Sum Condition
題目描述：
給定整數陣列 nums 和目標值 target。回傳非空子序列的數量，使得子序列的最小值加最大值不超過 target（結果取模 10^9+7）。
解題思路： 關鍵觀察：子序列的最小值和最大值只取決於子序列中包含哪些元素，而非順序。所以排序不影響結果。
排序後使用雙指標：
- 左指標
left從頭開始，右指標right從尾開始。 - 若
nums[left] + nums[right] <= target：以nums[left]為最小值的合法子序列，最大值可以是left到right之間的任何元素。中間的right - left個元素（不含 left 本身）每個可選或不選，共2^(right-left)個子序列。將此數量加入答案，left++。 - 若總和超過 target：right-- 縮小最大值。
需要預計算 2 的冪次以避免重複計算。
C++ 解法
複雜度分析
時間複雜度：O(n log n) — 排序 O(n log n)，雙指標遍歷 O(n)，預計算冪次 O(n)。
空間複雜度：O(n) — 儲存 2 的冪次陣列。
虛擬碼
1. Sort nums in ascending order
2. Precompute pow2[i] = 2^i mod MOD for i = 0 to n-1
3. Set left = 0, right = n - 1, ans = 0
4. While left <= right:
a. If nums[left] + nums[right] <= target:
- ans += pow2[right - left] (mod MOD)
- left++
b. Else:
- right--
5. Return ans其他解法
排序 + 二分搜尋 O(n log n)：對每個左端點 i，二分搜尋最大的右端點 j 使得 nums[i] + nums[j] <= target，然後加上 2^(j-i) 個子序列。時間 O(n log n)，與雙指標等價但實作稍不同。
暴力枚舉 O(2^n)：列舉所有子序列，檢查最小值+最大值條件。僅適合 n 極小的情況。
延伸思考
- 為什麼排序不會改變子序列的計數結果？如何嚴謹證明？
- 若條件改為「最大值減最小值不超過 target」，雙指標法是否仍適用？
- 若要求子序列長度至少為 k，如何修改計算方式？