手撕 | 最长无重复子数组

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
}