number-of-subsequences-that-satisfy-the-given-sum-condition

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array of integers <code>nums</code> and an integer <code>target</code>.

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

&nbsp;
Example 1:

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

Example 2:

<pre>
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]
</pre>

Example 3:

<pre>
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).
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 106</code></li>
	<li><code>1 &lt;= target &lt;= 106</code></li>
</ul>

numSubseq

Number of Subsequences That Satisfy the Given Sum Condition

Minimum Operations to Form Subsequence With Target Sum

minimum-operations-to-form-subsequence-with-target-sum

使子序列的和等于目标的最少操作次数

Find the Sum of Subsequence Powers

find-the-sum-of-subsequence-powers

求出所有子序列的能量和

Find the Sum of the Power of All Subsequences

find-the-sum-of-the-power-of-all-subsequences

Array

Two Pointers

Binary Search

Sorting

给你一个整数数组 <code>nums</code> 和一个整数 <code>target</code> 。

请你统计并返回 <code>nums</code> 中能满足其最小元素与最大元素的 和 小于或等于 <code>target</code> 的 非空 子序列的数目。

由于答案可能很大，请将结果对<meta charset="UTF-8" />&nbsp;<code>109&nbsp;+ 7</code>&nbsp;取余后返回。

&nbsp;

示例 1：

<pre>
输入：nums = [3,5,6,7], target = 9
输出：4
解释：有 4 个子序列满足该条件。
[3] -&gt; 最小元素 + 最大元素 &lt;= target (3 + 3 &lt;= 9)
[3,5] -&gt; (3 + 5 &lt;= 9)
[3,5,6] -&gt; (3 + 6 &lt;= 9)
[3,6] -&gt; (3 + 6 &lt;= 9)
</pre>

示例 2：

<pre>
输入：nums = [3,3,6,8], target = 10
输出：6
解释：有 6 个子序列满足该条件。（nums 中可以有重复数字）
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]</pre>

示例 3：

<pre>
输入：nums = [2,3,3,4,6,7], target = 12
输出：61
解释：共有 63 个非空子序列，其中 2 个不满足条件（[6,7], [7]）
有效序列总数为（63 - 2 = 61）
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 106</code></li>
	<li><code>1 &lt;= target &lt;= 106</code></li>
</ul>