Leetcode 1498. Number of Subsequences That Satisfy the Given Sum Condition

題目描述

You are given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal to target. Since the answer may be too large, return it modulo 10^9 + 7.

範例

Example 1:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

Example 2:

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

### Example 3:

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them do not satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6
• 1 <= target <= 10^6

解法

two poiner

1. sort (由小到大)
2. two pointer 一個從左一個從右邊找到 arr[i] + arr[j] <= k
3. 如果 arr[i] + arr[j] <= k 代表最小值還能增加，移動左指針，反之移動右指針，讓 arr[i] + arr[j] 變小
4. 計算這個區間中的 subsequence 有多少，加到答案裡面

func numSubseq(nums []int, target int) int {
    const MOD = 1_000_000_007
    sort.Ints(nums)

    n := len(nums)
    pow2 := make([]int, n+1)
    pow2[0] = 1
    for i:=1; i<=n; i++ {
        pow2[i] = pow2[i-1]*2 % MOD
    }

    res := 0
    l, r := 0, n-1
    for l <= r {
        if nums[l] + nums[r] <= target {
            res += pow2[r-l]
            res %= MOD
            l++
        } else {
            r--
        }
    }

    return res
}

計算子集合

從 nums[l+1] 到 nums[r] 這段長度為 r - l 中挑選任意個元素（可以不挑），總共會有 2^(r - l) 個子集合（不包含 nums[l]）

為啥不包含 nums[l] ?

這些子集合的前提是我們已經固定選了 nums[l]（因為我們要它當「最小值」）。固定選 nums[l]（最小值），然後從 nums[l+1..r] 這段中挑選 0~(r-l) 個元素，這 2^(r - l) 個子序列都是合法的。

為啥不能包含 nums[l] ?

1. 如果你把 nums[l] 也當成「可選或不選」的一部分，那就會錯，因為會重複計算那些不包含 nums[l] 的子序列
2. 那些子序列可能會有最小值更大的元素，這違反我們當前判斷是以 nums[l] 為「最小值」的條件