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

最长无重复子数组

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



public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        if(arr == null){
            return 0;
        }
        if(arr.length == 1){
            return 1;
        }
        int n = arr.length;
        HashMap<Integer,Integer> map = new HashMap<>();
        int result = 0;
        int left = -1;
        //窗口从[left,0] 开始
        for(int right = 0; right < n;right ++){
            //如果这个数字之前有,看下之前的这个数字位置和left 哪个大选哪个
            if(map.containsKey(arr[right])){
                left = Math.max(left, map.get(arr[right]));
            }
            //更新窗口
            result = Math.max(result, right - left);
            map.put(arr[right], right);
        }
        
//         int result = 0;
//         int start=0;
//         int [] last=new int[100000]; // 价值等同于map
//         for(int i = 0;i< n;i++){
//             int index = arr[i];
//             //last[index]->上次出现的位置不能重复需要加
//             start = Math.max(start,last[index]);
//             result = Math.max(result,i - start + 1);
//             last[index] = i+ 1;
//         }
        return result;
    }
}
全部评论

相关推荐

2024-12-26 20:46
复旦大学 C++
国棉17厂丶小王:拿了offer的那个周末晚上去网吧通宵,去网吧不知道玩什么刷了lc的每日一题,然后试着第一次打开了三角洲行动,从此少了一个已经刷了700道题的lc用户,但是烽火地带多了一只🐭🐭
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务