find-the-k-sum-of-an-array

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 integer array <code>nums</code> and a positive integer <code>k</code>. You can choose any subsequence of the array and sum all of its elements together.

We define the K-Sum of the array as the <code>kth</code> largest subsequence sum that can be obtained (not necessarily distinct).

Return the K-Sum of the array.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Note that the empty subsequence is considered to have a sum of <code>0</code>.

&nbsp;
Example 1:

<pre>
Input: nums = [2,4,-2], k = 5
Output: 2
Explanation: All the possible subsequence sums that we can obtain are the following sorted in decreasing order:
- 6, 4, 4, 2, 2, 0, 0, -2.
The 5-Sum of the array is 2.
</pre>

Example 2:

<pre>
Input: nums = [1,-2,3,4,-10,12], k = 16
Output: 10
Explanation: The 16-Sum of the array is 10.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>-109 &lt;= nums[i] &lt;= 109</code></li>
	<li><code>1 &lt;= k &lt;= min(2000, 2n)</code></li>
</ul>

kSum

Find the K-Sum of an Array

Array

Sorting

Heap (Priority Queue)

给你一个整数数组 <code>nums</code> 和一个 正 整数 <code>k</code> 。你可以选择数组的任一 子序列 并且对其全部元素求和。

数组的 第 k 大和 定义为：可以获得的第 <code>k</code> 个 最大 子序列和（子序列和允许出现重复）

返回数组的 第 k 大和 。

子序列是一个可以由其他数组删除某些或不删除元素派生而来的数组，且派生过程不改变剩余元素的顺序。

注意：空子序列的和视作 <code>0</code> 。

&nbsp;

示例 1：

<pre>
输入：nums = [2,4,-2], k = 5
输出：2
解释：所有可能获得的子序列和列出如下，按递减顺序排列：
6、4、4、2、2、0、0、-2
数组的第 5 大和是 2 。
</pre>

示例 2：

<pre>
输入：nums = [1,-2,3,4,-10,12], k = 16
输出：10
解释：数组的第 16 大和是 10 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>-109 &lt;= nums[i] &lt;= 109</code></li>
	<li><code>1 &lt;= k &lt;= min(2000, 2n)</code></li>
</ul>