題目描述:
給定整數陣列 nums 和目標值 target。回傳非空子序列的數量,使得子序列的最小值加最大值不超過 target(結果取模 10^9+7)。
解題思路: 關鍵觀察:子序列的最小值和最大值只取決於子序列中包含哪些元素,而非順序。所以排序不影響結果。
排序後使用雙指標:
left 從頭開始,右指標 right 從尾開始。nums[left] + nums[right] <= target:以 nums[left] 為最小值的合法子序列,最大值可以是 left 到 right 之間的任何元素。中間的 right - left 個元素(不含 left 本身)每個可選或不選,共 2^(right-left) 個子序列。將此數量加入答案,left++。需要預計算 2 的冪次以避免重複計算。
時間複雜度: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 極小的情況。