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

最长无重复子数组

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

import java.util.*;

public class Solution {
    /**
     *
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        int[] chars = arr;
        if (chars.length == 0) return 0;
        // 用来保存每一个字符上一次出现的位置
        Map<Integer, Integer> prevIdxes = new HashMap<>();
        prevIdxes.put(chars[0], 0);
        // 以i - 1位置字符结尾的最长不重复字符串的开始索引(最左索引)
        int li = 0;
        // max 记录
        int max = 1;
        for (int i = 1; i < chars.length; i++) {
            // i位置字符上一次出现的位置
            Integer pi = prevIdxes.get(chars[i]);
            if (pi != null &&
                    li <= pi) { // 小于或者等于最左记录的索引时,直接就是更新li的值
                // li最左位置小于或者等于字符上一次重复的位置,则直接是li为重复字符索引pi+1
                li = pi + 1;
            }
            // li最左位置大于字符上一次重复的位置,则直接是li到i
            // 存储这个字符出现的位置
            prevIdxes.put(chars[i], i);
            // 求出最长不重复子串的长度
            max = Math.max(max, i - li + 1);
        }
        return max;
    }
}

解题思想:滑动窗口

#算法笔记##算法#
全部评论
大佬解释的很到位啊
点赞 回复 分享
发布于 2023-05-26 21:21 湖北
能看到这篇题解,是我三生有幸
点赞 回复 分享
发布于 2023-05-26 21:15 甘肃

相关推荐

强大的马里奥:不太可能,我校计算机硕士就业率99%
点赞 评论 收藏
分享
那一天的Java_J...:他本来公司就是做这个的,不就是正常的游戏客户端和服务器开发,软硬件联动,有啥恶心不恶心的,提前告诉你就是怕你接受不了,接受不了就没必要再往后走流程浪费时间,虽然这公司是一坨。
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务