目 录CONTENT

文章目录

手撕 | 最长无重复子数组

RobKing
2023-09-24 / 0 评论 / 0 点赞 / 182 阅读 / 528 字

手撕 | 最长无重复子数组

NC41 最长无重复子数组

给定一个长度为n的数组arr,返回arr的最长无重复元素子数组的长度,无重复指的是所有数字都不相同。

子数组是连续的,比如[1,3,5,7,9]的子数组有[1,3],[3,5,7]等等,但是[1,3,7]不是子数组

思路: 滑动窗口+map去重

  • 维护一个滑动窗口,窗口内的元素不可以重复
  • 通过 map 来保证窗口无重复元素,当有重复元素的时候,需要遍历将这个重复元素之前的全部删除,然后更新最新的位置
  • 一种更好的思路就是直接更新左边界即可,不用删除重复元素,可以避免回到之前的位置
  • 每次遍历之后 首先判断是否有重复元素,然后再进行更新答案
package main

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param arr int整型一维数组 the array
 * @return int整型
*/
func maxLength( arr []int ) int {
    // write code here
    // 思路:维护一个滑动窗口,通过map判断是否重复
    size := len(arr)
    if size == 0 {
        return 0
    }
    m := make(map[int]int)
    res := 0
    i := 0
    for j := 0; j < size; j ++ {
        // 判断是否存在
        if k, ok := m[arr[j]]; ok {
            i = max(i, k + 1)
        }
        m[arr[j]] = j
        res = max(res, j - i + 1)
    }
    return res
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

利用同样的思路解决以下的题目

3. 无重复字符的最长子串

func lengthOfLongestSubstring(s string) int {
    size := len(s)
    if size == 0 {
        return 0
    }
    m := make(map[byte]int)
    res, i := 0, 0
    for j := range s {
        if k, ok := m[s[j]]; ok {
            // 只需要更新左边界,无需删除重复的元素
            // 重复的时候会 避免左边界 到之前的位置 "abcb"
            i = max(i, k + 1)
        }
        m[s[j]] = j
        res = max(res, j - i + 1)
    }
    return res
}

func max(x, y int) int {
    if x >y {
        return x
    }
    return y
}
0

评论区