LeetCode 腾讯精选50题--子集

傷城~ 2023-06-05 05:53 5阅读 0赞

根据题意，找到几何中的所有子集，说实话子集是没有什么头绪的，因为如果采用遍历的方法，稍有遗漏不说，代码的嵌套循环层数随着数组大小的增加而增加，想了很久没有头绪后就去看了看评论，然后就被点破了解题的关键：遍历数组时，让当前这一元素构成的集合，分别去加上之前找到的所有子集，由于第一次找到的子集一定有两个，一个为空，一个带有一个元素，那么用当前元素组成的集合分别加上之前的集合，一定会有一个集合只有当前元素

如图：

![1475689-20190808202147987-1113081148.png][]

由于采用遍历的方式，对于数组长度为N，指针没往前走一次，要遍历的子集数量是原来的2倍，所以此算法的时间复杂度就是等比数列求和后的复杂度，即为O(2^N)

以下是代码：

1 package algorithm;
     2 
     3 import java.util.ArrayList;
     4 import java.util.List;
     5 
     6 public class SubCollection {
     7     public List<List<Integer>> subsets(int[] nums) {
     8 
     9         List<List<Integer>> totalSubLists = new ArrayList<>();
    10 
    11         for (int i = nums.length-1; i >=0; i--) {
    12             if(totalSubLists.size()==0){
    13                 List<Integer> self = new ArrayList<>();
    14                 self.add(nums[i]);
    15                 totalSubLists.add(self);
    16                 totalSubLists.add(new ArrayList<>());
    17             }else {
    18                 int size = totalSubLists.size();
    19                 int se=0;
    20                 while (true){
    21                     List<Integer> self = new ArrayList<>();
    22                     self.add(nums[i]);
    23                     self.addAll(totalSubLists.get(se++));
    24                     totalSubLists.add(self);
    25                     if(se >= size){
    26                         break;
    27                     }
    28 
    29                 }
    30             }
    31         }
    32         
    33         return totalSubLists;
    34     }
    35 
    36 }

转载于:https://www.cnblogs.com/Kaithy-Rookie/p/11323603.html

[1475689-20190808202147987-1113081148.png]: /images/20230601/667b15a4b0b740de86cf830d8f7ab73b.png