1498. Number of Subsequences That Satisfy the Given Sum Condition

題意

給一個數字陣列，計算出 subsequence 中最大與最小元素相加後不大於 target 的 subsequence 總數

• 回傳型別為int，避免overflow答案需要 mod $10^9 + 7$

• 空陣列不算答案

限制

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^6

• 1 <= target <= 10^6

思考

• subsequence，並且只計算總數，不需要記得數字順序

  • 每個數字選或不選的排列組合問題

  • 需要取得subsequence的最大及最小值 ⇒ 不需要記憶順序即可 sort，並取 subarray 頭尾便可知道是否符合 subarray.front() + subarray.back() <= target

• 排序後符合條件的，長度為$N$ 的 subarray

  • 固定頭或尾其中一個數字，確保subarray符合條件，總共可以取出 $2^{N-1}$ 種結果 ($N-1$ 個數字可以取或不取)

• 假如input總長為 $N$，為了節省每次計算pow的時間，可以預先計算 $2^0$ 到 $2^{N-1}$ 的所有數字供查表

• 利用two pointer來找出所有可能的 subarray

Solution

#define M 1000000007

class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        const int n = nums.size();
        sort(nums.begin(), nums.end());

        vector<int> pows(n, 1);
        for (int i = 1; i < n; i += 1) {
            pows[i] = (pows[i - 1] << 1) % M;
        }

        int ans = 0;
        int i = 0;
        int j = n - 1;
        while (i <= j) {
            if (nums[i] + nums[j] > target) {
                j -= 1;
            } else {
                ans = (ans + pows[j - i]) % M;
                i += 1;
            }
        }
        return ans;
    }
};