spring自定义注解

491. 递增子序列

难度中等216收藏分享切换为英文接收动态反馈

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是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]]

说明:

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

通过次数29,313

提交次数52,378

题解

class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        Set<List<Integer>> res = new HashSet<>();
        if( nums == null || nums.length == 0){
            return new ArrayList<>(res);
        } 
        traceBack(nums, 0, new LinkedList<Integer>(), res);
        return new ArrayList<>(res);
    }

    void traceBack(int[] nums, int start, LinkedList<Integer> temp, Set<List<Integer>> res){
        if(temp.size() > 1){
            res.add(new LinkedList<Integer>(temp));
        }
        for(int i =start; i < nums.length; i++){
            if(temp.size() > nums.length) break;
            //if( i > start && nums[i] ==nums[i-1]) continue;
            if( temp.isEmpty() || temp.peekLast() <= nums[i]){
                temp.add(nums[i]);
                traceBack(nums, i+1, temp, res);
                temp.pollLast();
            } 
        }
    }
}

if( i > start && nums[i] ==nums[i-1]) continue; 这段也可以用作去重， 但是需要在res.add(new LinkedList<Integer>(temp)); 后添加return , 否则只能去掉 相邻的2个重复数字，

例如 ：1，1, 1 ,1 只能去掉 第2个1 ,只能利用hashset进行去重处理。

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 mym_74@163.com