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 than 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 don't satisfy the condition ([6,7], [7]). Number of valid subsequences (63 - 2 = 61).
Example 4:
Input: nums = [5,2,4,1,7,6,8], target = 16 Output: 127 Explanation: All non-empty subset satisfy the condition (2^7 - 1) = 127
Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1 <= target <= 10^6
Solution: Two Pointers
Since order of the elements in the subsequence doesn’t matter, we can sort the input array.
Very similar to two sum, we use two pointers (i, j) to maintain a window, s.t. nums[i] +nums[j] <= target.
Then fix nums[i], any subset of (nums[i+1~j]) gives us a valid subsequence, thus we have 2^(j-(i+1)+1) = 2^(j-i) valid subsequence for window (i, j).
Time complexity: O(nlogn) // Sort
Space complexity: O(n) // need to precompute 2^n % kMod.
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua class Solution { public: int numSubseq(vector<int>& nums, int target) { constexpr int kMod = 1e9 + 7; const int n = nums.size(); vector<int> p(n + 1, 1); for (int i = 1; i <= n; ++i) p[i] = (p[i - 1] << 1) % kMod; sort(begin(nums), end(nums)); int ans = 0; for (int i = 0, j = n - 1; i <= j; ++i) { while (i <= j && nums[i] + nums[j] > target) --j; if (i > j) continue; // In subarray nums[i~j]: // min = nums[i], max = nums[j] // nums[i] + nums[j] <= target // {nums[i], (j - i - 1 + 1 values)} // Any subset of the right part gives a valid subsequence // in the original array. And There are 2^(j - i) ones. ans = (ans + p[j - i]) % kMod; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment