feat: solve No.1498

BaffinLee · BaffinLee · commit 07cee057a675 · 2023-05-06T23:54:39.000+08:00
diff --git a/1401-1500/1498. Number of Subsequences That Satisfy the Given Sum Condition.md b/1401-1500/1498. Number of Subsequences That Satisfy the Given Sum Condition.md
@@ -0,0 +1,98 @@
+# 1498. Number of Subsequences That Satisfy the Given Sum Condition
+
+- Difficulty: Medium.
+- Related Topics: Array, Two Pointers, Binary Search, Sorting.
+- Similar Questions: .
+
+## Problem
+
+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** `109 + 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 <= 105`
+	
+- `1 <= nums[i] <= 106`
+	
+- `1 <= target <= 106`
+
+
+
+## Solution
+
+```javascript
+/**
+ * @param {number[]} nums
+ * @param {number} target
+ * @return {number}
+ */
+var numSubseq = function(nums, target) {
+    nums.sort((a, b) => a - b);
+    var res = 0;
+    var l = 0;
+    var r = nums.length - 1;
+    var mod = Math.pow(10, 9) + 7;
+    var pows = Array(nums.length);
+    pows[0] = 1;
+    for (var i = 1; i < nums.length; i++) {
+        pows[i] = (pows[i - 1] * 2) % mod;
+    }
+    while (l <= r) {
+        if (nums[l] + nums[r] <= target) {
+            res += pows[r - l];
+            res %= mod;
+            l++;
+        } else {
+            r--;
+        }
+    }
+    return res;
+};
+```
+
+**Explain:**
+
+1. sort the array won't change the result, so we sort it first
+2. then use two pointer to find out answers
+3. keep it in mind: do not let numbers overflow
+
+**Complexity:**
+
+* Time complexity : O(nlog(n)).
+* Space complexity : O(n).
