题解 | #最长无重复子数组#

最长无重复子数组

http://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4

最长无重复子数组

描述

给定一个数组arr,返回arr的最长无重复元素子数组的长度,无重复指的是所有数字都不相同。
子数组是连续的,比如[1,3,5,7,9]的子数组有[1,3],[3,5,7]等等,但是[1,3,7]不是子数组。

思路

一开始是想用Set来做,遍历数组只要set中不包含该数字就添加,否则clear,继续遍历,重新添加。记录下最多元素的数量。
运行时发现有问题,不应该从出现重复数字的位置继续添加,而应该从出现重复数字时,该数字第一次出现的索引处继续遍历,重新添加。因此需要记录下每个元素的索引位置。于是使用Map来做。
Key存放数组元素,Value存放数组索引。
从索引0处开始遍历,当map中不包含该元素时,将该元素和该索引加入到map中。若map中已经包含了该元素,则得到该元素所在的索引,从该索引开始遍历,并且clear该map。记录下map最多元素时的数量,最后返回。

    public int maxLength (int[] arr) {
        //安全性分析
        if (arr == null) {
            return 0;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        //最大长度
        int maxLength = 0;
        //遍历数组
        for (int i = 0; i < arr.length; i++) {
            //当map中不含有该索引处的元素时
            if (!map.containsKey(arr[i])) {
                //记录下当前元素所在的索引
                map.put(arr[i], i);
                //不断更新最大长度
                if (map.size()>=maxLength) {
                    maxLength = map.size();
                }
            }else {
                //当map中含有该所引处的元素时,得到该索引赋值给i
                i = map.get(arr[i]);
                //清除map,从i索引处重新遍历
                map.clear();
            }
        }
        //返回最大值
        return maxLength;
    }

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-20 07:39
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-28 02:13
门头沟学院_2024
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议