题目描述

[EN | CN]

给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是 2。

示例:

1
2
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

说明:

  • 给定数组的长度不会超过 15
  • 数组中的整数范围是 [-100,100]
  • 给定数组中可能包含重复数字,相等的数字应该被视为递增的一种情况。

解法 1:BFS

用一个集合 rets 来维护所有的递增子序列,一开始假设只考虑数组 nums 的前 0 个元素,并每次多考虑 1 个元素,更新数组 rets。当多考虑一个元素时,若 rets 为空或者 rets[ -1] 小于当前元素,则可以将其加入到新的 rets 中。这里还要考虑到去重的问题,因为所有的 ret 里面的数字都是有序的,因此我们可以将其定为 tuple 类型,通过设置 rets 为集合类型,自动实现了去重。

复杂度分析略。

实现与结果如下:

1
2
3
4
5
6
7
8
class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        rets = {()}
        for num in nums:
            rets |= {ret + (num,)
                     for ret in rets
                     if len(ret) == 0 or ret[-1] <= num}
        return [list(ret) for ret in rets if len(ret) >= 2]
  • 执行用时:244 ms,在所有 Python3 提交中击败了 80.76% 的用户。
  • 内存消耗:24.4 MB,在所有 Python3 提交中击败了 100.00% 的用户。

解法 2:DFS