LeetCode刷题之HOT100之子集

本文主要是介绍LeetCode刷题之HOT100之子集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2024/6/11 周二，闷热，很热。两天没有做题了，前天去附近一景点《十八重溪》游玩，去了才知道暂停开放，只能在附近转转了，瀑布是看不到了。昨天在宿舍呆了一天，今天早上起来就来了实验室。补三张图就开始做题啦！
图一、十八重溪牌匾

图二、涓涓细流

图三、我的溯溪鞋派上了用场嘿嘿，水非常清澈呀
好啦，下面开始做题啦

1、题目描述

2、逻辑分析

这题给定一个整数数组nums，元素互不相同，要求返回做有可能的子集。怎么做呢？题解如是说：

因为nums大小不为0，故解集中一定有空集。令解集一开始只有空集，然后遍历nums，每遍历一个数字，拷贝解集中的所有子集，将该数字与这些拷贝组成新的子集再放入解集中即可

1. 例如[1,2,3]，一开始解集为[[]]，表示只有一个空集。
2. 遍历到1时，依次拷贝解集中所有子集，只有[]，把1加入拷贝的子集中得到[1]，然后加回解集中。此时解集为
   [[], [1]]。
3. 遍历到2时，依次拷贝解集中所有子集，有[], [1]，把2加入拷贝的子集得到[2], [1, 2]，然后加回解集中。此时解集为
   [[], [1], [2], [1, 2]]。
4. 遍历到3时，依次拷贝解集中所有子集，有[], [1], [2], [1, 2]，把3加入拷贝的子集得到[3], [1, 3], [2,3], [1, 2, 3]，然后加回解 集中。此时解集为[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]。

以上规律即可写出相应代码

3、代码演示

public List<List<Integer>> subsets(int[] nums) {// 创建一个空的二维列表 res，用于存储 nums 的所有可能子集List<List<Integer>> res = new ArrayList<>();// 初始时，将一个空集（即不包含任何元素的子集）添加到 res 中  // 因为空集是任何集合的子集，包括 nums  res.add(new ArrayList<Integer>());// 遍历 nums 数组中的每一个元素for(int i = 0; i < nums.length; i++){// subNum 存储在添加当前元素 nums[i] 之前，res 中已有的子集数量  // 这是因为我们接下来要基于这些已有的子集来生成新的子集  int subNum = res.size();// 遍历 res 中已有的每一个子集for(int j = 0; j < subNum; j++){// 复制当前遍历到的子集，避免在后续操作中修改原始子集List<Integer> list = new ArrayList<>(res.get(j));// 将当前元素 nums[i] 添加到复制的子集中，生成一个新的子集list.add(nums[i]);// 将新生成的子集添加到 res 中 res.add(list);}}// 返回包含 nums 所有可能子集的二维列表return res;}

以上是代码的描述，上面注释很清晰，就不过多赘述。

4、复杂度分析

• 时间复杂度：$O(n\times 2^n)$，算法中使用了两个嵌套的循环。
  对于外层循环，每次迭代都会处理数组nums中的一个新元素，因此外层循环的复杂度是O(n)，其中n是数组nums的长度。
  对于内层循环，其复杂度依赖于当前res列表中已有子集的数量。在第一次迭代时，res中只有一个空集，因此内层循环执行一次。在第二次迭代时，res中有两个子集（一个空集和一个只包含nums[0]的子集），因此内层循环执行两次。依此类推，每次外层循环迭代时，内层循环执行的次数都会翻倍。因此，内层循环的总执行次数是1+ 2 + 4 + … + 2^(n-1)， 其和为2^n - 1。故时间复杂度为$O(n\times 2^n)$。

• 空间复杂度：$O(n\times 2^n)$。在最坏的情况下，即数组nums的所有可能子集都被生成时，res列表将包含2^n个子集 （包括空集）。每个子集都是一个ArrayList实例，它们将占据额外的空间。因此，空间复杂度是O(2^n)， 因为我们需要存储2^n个子集。

over，再见！

这篇关于LeetCode刷题之HOT100之子集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---