个人主页代码不加冰欢迎来访作者简介java后端学习者❄️个人专栏LeetCode刷题日记 苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰这周过完就正式进入痛苦的期末周了文章平时也没什么时间写只能每天抽出一点时间刷几题算法和看看八股没事的时候还是用cc跑了几个项目然后跑了个自用的时间管理软件还是挺好玩的废话不多说进入到我们的今日刷题环节摘要题目背景491.递增子序列给你一个整数数组nums找出并返回所有该数组中不同的递增子序列递增子序列中至少有两个元素。你可以按任意顺序返回答案。数组中可能含有重复元素如出现两个整数相等也可以视作递增序列的一种特殊情况。示例 1输入nums [4,6,7,7]输出[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]示例 2输入nums [4,4,3,2,1]输出[[4,4]]提示1 nums.length 15-100 nums[i] 100题目解析首先题目要求给定一个整数数组nums找出所有不同的递增子序列长度至少为2。这里的递增指的是nums[i] nums[j]注意不是连续子数组是子序列可以跳过元素结果不能有重复序列但是数组中可以有重复的元素我们一眼看出来是回溯类型的题目和我们前面做的子集问题类似但是去重的思路不一样。本质区别总结力扣90子集可以排序 排序后 重复元素连续 树层去重 if(i startIndex nums[i] nums[i-1]) 利用排序去重本题不能排序 重复元素可能分散 树层去重 HashSetInteger used 记录本层已经使用过的数字可以这样记题目是否排序去重方式90 子集Ⅱ可以nums[i]nums[i-1]40 组合总和Ⅱ可以nums[i]nums[i-1]47 全排列Ⅱ可以nums[i]nums[i-1] used[]491 递增子序列不能HashSet树层去重所以这道题目不能排序题目要的是递增的子序列如果对原来的数组进行排序结果就完全不一样了例如{1354}结果[1,3],[1,5],[1,4],[3,5],[3,4],[1,3,5],[1,3,4]{5341}结果[[3,4]]这两个的结果完全不一样。回溯三部曲参数需要知道当前遍历到哪里 当前路径因此backtracking(nums,startIndex)终止条件题目要求长度 2所以path.size() 2就加入结果集。注意这里不能 return。因为后面可能还能继续选。例如[4,6]还能扩展成[4,6,7]所以if(path.size() 2){ result.add(...) }继续向下搜索。单层搜索逻辑遍历当前位置后面的所有元素for(int istartIndex;inums.length;i)如何保证递增当前数字nums[i]要大于等于路径最后一个数字nums[i] path最后一个元素否则跳过if(!path.isEmpty() nums[i] path.get(path.size()-1)) { continue; }本题最大难点去重看看这个例子[4,6,7,7]假设第一层4 6 7 7如果两个 7 都选[4,7]会出现两次。因此同一树层不能出现相同数字同一树枝可以例如[7,7]是合法答案。树层去重使用 HashSet每一层创建一个HashSetInteger used new HashSet();如果本层已经出现used.contains(nums[i])直接跳过if(used.contains(nums[i])){ continue; }然后记录used.add(nums[i]);为什么不能全局 HashSet例如[7,7]第一个7用了。第二个7如果全局去重直接被过滤结果[7,7]永远出不来。所以只能树层去重 不能全局去重这是本题核心。我们可能会想if(i startIndex nums[i] nums[i - 1]){ continue; }90子集之所以能用if(i startIndex nums[i] nums[i - 1])是因为题目允许先排序排序后相同元素一定挨在一起所以只要发现当前元素和前一个元素相同就说明这是同一层的重复选择可以直接跳过。而力扣491要求求递增子序列必须保持原数组的相对顺序不能排序相同元素可能分散在数组的不同位置例如[4,7,6,7]中两个7中间隔着一个6此时nums[i] nums[i-1]根本检测不到重复因此90题的去重方式失效。491只能使用HashSet记录当前树层已经使用过的数字只要这一层出现过某个数字后面再遇到相同数字就跳过从而实现树层去重。简单来说90是利用排序后“相同元素连续”的特性去重491是利用HashSet记录“当前层出现过哪些值”去重。题目答案class Solution { ListListInteger result new ArrayList(); LinkedListInteger path new LinkedList(); public ListListInteger subsetsWithDup(int[] nums) { Arrays.sort(nums); backtracking(nums, 0); return result; } private void backtracking(int[] nums, int startIndex) { result.add(new ArrayList(path)); for (int i startIndex; i nums.length; i) { // 树层去重 if (i startIndex nums[i] nums[i - 1]) { continue; } path.add(nums[i]); backtracking(nums, i 1); path.removeLast(); } } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励
【LeetCode刷题日记】491.递增子序列 一篇搞懂
发布时间：2026/6/12 1:51:23
个人主页代码不加冰欢迎来访作者简介java后端学习者❄️个人专栏LeetCode刷题日记 苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰这周过完就正式进入痛苦的期末周了文章平时也没什么时间写只能每天抽出一点时间刷几题算法和看看八股没事的时候还是用cc跑了几个项目然后跑了个自用的时间管理软件还是挺好玩的废话不多说进入到我们的今日刷题环节摘要题目背景491.递增子序列给你一个整数数组nums找出并返回所有该数组中不同的递增子序列递增子序列中至少有两个元素。你可以按任意顺序返回答案。数组中可能含有重复元素如出现两个整数相等也可以视作递增序列的一种特殊情况。示例 1输入nums [4,6,7,7]输出[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]示例 2输入nums [4,4,3,2,1]输出[[4,4]]提示1 nums.length 15-100 nums[i] 100题目解析首先题目要求给定一个整数数组nums找出所有不同的递增子序列长度至少为2。这里的递增指的是nums[i] nums[j]注意不是连续子数组是子序列可以跳过元素结果不能有重复序列但是数组中可以有重复的元素我们一眼看出来是回溯类型的题目和我们前面做的子集问题类似但是去重的思路不一样。本质区别总结力扣90子集可以排序 排序后 重复元素连续 树层去重 if(i startIndex nums[i] nums[i-1]) 利用排序去重本题不能排序 重复元素可能分散 树层去重 HashSetInteger used 记录本层已经使用过的数字可以这样记题目是否排序去重方式90 子集Ⅱ可以nums[i]nums[i-1]40 组合总和Ⅱ可以nums[i]nums[i-1]47 全排列Ⅱ可以nums[i]nums[i-1] used[]491 递增子序列不能HashSet树层去重所以这道题目不能排序题目要的是递增的子序列如果对原来的数组进行排序结果就完全不一样了例如{1354}结果[1,3],[1,5],[1,4],[3,5],[3,4],[1,3,5],[1,3,4]{5341}结果[[3,4]]这两个的结果完全不一样。回溯三部曲参数需要知道当前遍历到哪里 当前路径因此backtracking(nums,startIndex)终止条件题目要求长度 2所以path.size() 2就加入结果集。注意这里不能 return。因为后面可能还能继续选。例如[4,6]还能扩展成[4,6,7]所以if(path.size() 2){ result.add(...) }继续向下搜索。单层搜索逻辑遍历当前位置后面的所有元素for(int istartIndex;inums.length;i)如何保证递增当前数字nums[i]要大于等于路径最后一个数字nums[i] path最后一个元素否则跳过if(!path.isEmpty() nums[i] path.get(path.size()-1)) { continue; }本题最大难点去重看看这个例子[4,6,7,7]假设第一层4 6 7 7如果两个 7 都选[4,7]会出现两次。因此同一树层不能出现相同数字同一树枝可以例如[7,7]是合法答案。树层去重使用 HashSet每一层创建一个HashSetInteger used new HashSet();如果本层已经出现used.contains(nums[i])直接跳过if(used.contains(nums[i])){ continue; }然后记录used.add(nums[i]);为什么不能全局 HashSet例如[7,7]第一个7用了。第二个7如果全局去重直接被过滤结果[7,7]永远出不来。所以只能树层去重 不能全局去重这是本题核心。我们可能会想if(i startIndex nums[i] nums[i - 1]){ continue; }90子集之所以能用if(i startIndex nums[i] nums[i - 1])是因为题目允许先排序排序后相同元素一定挨在一起所以只要发现当前元素和前一个元素相同就说明这是同一层的重复选择可以直接跳过。而力扣491要求求递增子序列必须保持原数组的相对顺序不能排序相同元素可能分散在数组的不同位置例如[4,7,6,7]中两个7中间隔着一个6此时nums[i] nums[i-1]根本检测不到重复因此90题的去重方式失效。491只能使用HashSet记录当前树层已经使用过的数字只要这一层出现过某个数字后面再遇到相同数字就跳过从而实现树层去重。简单来说90是利用排序后“相同元素连续”的特性去重491是利用HashSet记录“当前层出现过哪些值”去重。题目答案class Solution { ListListInteger result new ArrayList(); LinkedListInteger path new LinkedList(); public ListListInteger subsetsWithDup(int[] nums) { Arrays.sort(nums); backtracking(nums, 0); return result; } private void backtracking(int[] nums, int startIndex) { result.add(new ArrayList(path)); for (int i startIndex; i nums.length; i) { // 树层去重 if (i startIndex nums[i] nums[i - 1]) { continue; } path.add(nums[i]); backtracking(nums, i 1); path.removeLast(); } } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励
