写点什么

LeetCode 题解:90. 子集 II,迭代,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 11 月 04 日
LeetCode题解:90. 子集 II,迭代,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/subsets-ii/


解题思路:


  1. 生成所有子集,实际上要达到的效果是,nums 中的每个元素是否显示在子集中。

  2. 假设现在已经生成了 n-1 个元素的子集,当前遍历到第 n 个元素,那么只需要将现有的子集遍历一次,将第 n 个元素加入到现有子集中,形成新的子集即可。

  3. 如何去重:

* 关于去重的方法,可以参考题解详细通俗的思路分析,多解法中的迭代法部分,结合我的注释加深理解。

* 如果在不去重的情况下,观察[1, 2, 2]的所有子集如下:


数组 [ 1 2 2 ] [ ] 的所有子集 [ ][ 1 ] 的所有子集 [ ] [ 1 ] [ 1 2 ] 的所有子集 [ ] [ 1 ] [ 2 ][ 1 2 ][ 1 2 2 ] 的所有子集 [ ] [ 1 ] [ 2 ] [ 1 2 ] [ 2 ] [ 1 2 ] [ 2 2 ] [ 1 2 2 ] 
复制代码


会发现[ 1 2 2 ] 的所有子串 [ ] [ 1 ] [ 2 ] [ 1 2 ] [ 2 ] [ 1 2 ] [ 2 2 ] [ 1 2 2 ] 中,重复的子集是[ 2 ] [ 1 2 ],而它们是由[ 1 ] 的所有子集 [ ] [ 1 ] 分别加上2得到的。

因此我们要做的是,在输出[ 1 2 2 ]的子集时,排除掉[ 1 ]的子集。

具体做法就是先保存[ 1 ]的所有子集长度,然后在第二层遍历中排除掉这部分子集。

同时需要判断nums[i] === nums[i - 1],也就是当出现重复元素时,才进行去重,

因为第一次遍历该元素时,已经输出过一次子集。


/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsetsWithDup = function (nums) {
// 储存结果的数组
// 初始状态要含有一个空数组,即无任何元素的子集
// 空数组的存在是为了开启第二层循环
let result = [[]]; // 存储最终结果
let lastTwoResultLength = 0; // 存储上上次的子集数量
nums.sort((a, b) => a - b); // 将nums排序,保证能够有效去重
// 每次从nums中取出一个元素,作为新子集的元素
for (let i = 0; i < nums.length; i++) {
// 获取当前的子集数量进行遍历,避免循环过程中result长度不断变化
let resultLength = result.length;
// 在现有子集的基础上,添加当前元素,生成新的子集
for (let j = 0; j < resultLength; j++) {
if (
// 当不是第一次遇到该元素时,才进行去重
nums[i] === nums[i - 1] &&
// 过滤掉上一次已经重复输出过子集 的情况
j < lastTwoResultLength) {
// 跳过当前元素,继续输出下一种 元素的子集
continue;
}
result.push([...result[j], nums[i]]);
}
// 存储上一次的子集数量
lastTwoResultLength = resultLength;
}
return result;
};
复制代码


发布于: 2020 年 11 月 04 日阅读数: 29
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:90. 子集 II,迭代,JavaScript,详细注释