What is the main algorithmic pattern used in this problem?

This problem primarily involves the combination of array manipulation, sorting, and heap usage to efficiently find the kth largest subsequence sum.

How do I efficiently find the kth largest subsequence sum?

You can use a heap to store the largest subsequence sums and pop smaller sums as you compute them, allowing you to quickly access the kth largest.

What is the time complexity of the brute force solution?

The brute force solution involves generating all subsequences and sorting their sums, leading to a time complexity of O(2^n log(2^n)).

How do negative numbers affect this problem?

Negative numbers can influence the sums of subsequences, but the approach still applies, as we are concerned with sorting the sums and selecting the kth largest value.

Can this problem be solved without sorting?

Sorting is the most straightforward method, but alternatives, such as using a max heap, can be employed to reduce time complexity when k is much smaller than the number of subsequences.

#2386

Hard

auto_awesome数组·排序

LeetCode 题解工作台

找出数组的第 K 大和

给你一个整数数组 nums 和一个正整数 k 。你可以选择数组的任一子序列并且对其全部元素求和。数组的第 k 大和定义为：可以获得的第 k 个最大子序列和（子序列和允许出现重复）返回数组的第 k 大和。子序列是一个可以由其他数组删除某些或不删除元素派生而来的数组，且派生过程…

数组排序堆（优先队列）

题目描述

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

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

返回数组的 第 k 大和 。

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

注意：空子序列的和视作 0 。

示例 1：

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

示例 2：

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

提示：

n == nums.length
1 <= n <= 10⁵
-10⁹ <= nums[i] <= 10⁹
1 <= k <= min(2000, 2ⁿ)

lightbulb

解题思路

方法一：优先队列（小根堆）

首先，我们找到最大的子序和 $mx$ ，即所有正数之和。

可以发现，其他子序列的和，都可以看成在这个最大子序列和之上，减去其他部分子序列之和得到。因此，我们可以将问题转换为求第 $k$ 小的子序列和。

只需要将所有数的绝对值升序排列，之后建立小根堆，存储二元组 $(s, i)$ ，表示当前和为 $s$ ，且下一个待选择的数字的下标为 $i$ 的子序列。

每次取出堆顶，并放入两种新情况：一是再选择下一位，二是选择下一位并且不选择本位。

由于数组是从小到大排序，这种方式能够不重不漏地按序遍历完所有的子序列和。

时间复杂度 $O(n \times \log n + k \times \log k)$ 。其中 $n$ 是数组 $\textit{nums}$ 的长度。空间复杂度 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def kSum(self, nums: List[int], k: int) -> int:
        mx = 0
        for i, x in enumerate(nums):
            if x > 0:
                mx += x
            else:
                nums[i] = -x
        nums.sort()
        h = [(0, 0)]
        for _ in range(k - 1):
            s, i = heappop(h)
            if i < len(nums):
                heappush(h, (s + nums[i], i + 1))
                if i:
                    heappush(h, (s + nums[i] - nums[i - 1], i + 1))
        return mx - h[0][0]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate uses a sorting-based approach to generate and retrieve subsequence sums.
question_mark
The candidate optimizes the problem with the use of heaps or other data structures.
question_mark
The candidate demonstrates knowledge of handling large input sizes by considering time complexity reductions.

warning

常见陷阱

外企场景

error
Generating all subsequences without considering the constraints of space and time complexity.
error
Overlooking the need for efficient sum retrieval and sorting or heap management.
error
Ignoring the requirement for handling repeated sums and selecting the correct kth value.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling arrays with both negative and positive values in a way that affects sum calculations.
arrow_right_alt
Optimizing the approach for very large arrays and values of k.
arrow_right_alt
Expanding the problem to include constraints on the subsequence size or type.

help

常见问题

外企场景

继续练习

#2402 会议室 III #2406 将区间分为最少组数 #2357 使数组中所有元素都等于零