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，並且只計算總數，不需要記得數字順序
  • 每個數字選或不選的排列組合問題
  • 只需要最大與最小值 ⇒ 不需要記憶順序即可 sort，並取 subarray 頭尾便可判斷是否符合 subarray.front() + subarray.back() <= target
• 排序後，若某個範圍（長度為 $N$）符合條件，則可以取出 $2^{N-1}$ 種結果（因為中間其他元素都可以自由選擇是否加入 subsequence）
• 為了節省每次計算 pow 的時間，可以預先計算 $2^0$ 到 $2^{N-1}$ 的所有數字（mod $10^9+7$）供查表
• 利用 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;
    }
};

時間與空間複雜度

• 時間複雜度
  先對陣列排序需要 O(Nlog⁡N)。接著使用 two pointer 往內縮的過程最多執行 O(N)次，每次計算都能在常數時間內完成。因此整體時間複雜度為 O(Nlog⁡N)。
• 空間複雜度
  需要一個長度為 N 的陣列來儲存預先計算的冪次（pows），因此空間複雜度為 O(N)。排序本身若使用原地排序，則不額外增加空間需求。