rustgym/leetcode/
_1498_number_of_subsequences_that_satisfy_the_given_sum_condition.rs

1struct Solution;
2
3const MOD: i32 = 1_000_000_007;
4
5impl Solution {
6    fn num_subseq(mut nums: Vec<i32>, target: i32) -> i32 {
7        nums.sort_unstable();
8        let mut res = 0;
9        let n = nums.len();
10        let mut power = vec![];
11        let mut prev = 1;
12        for _ in 0..n {
13            power.push(prev);
14            prev *= 2;
15            prev %= MOD;
16        }
17        let mut l = 0;
18        let mut r = n - 1;
19        while l <= r {
20            if nums[l] + nums[r] <= target {
21                res += power[r - l];
22                res %= MOD;
23                l += 1;
24            } else {
25                if r == 0 {
26                    break;
27                }
28                r -= 1;
29            }
30        }
31        res
32    }
33}
34
35#[test]
36fn test() {
37    let nums = vec![3, 5, 6, 7];
38    let target = 9;
39    let res = 4;
40    assert_eq!(Solution::num_subseq(nums, target), res);
41}