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

package main

/**
 * 
 * @param arr int整型一维数组 the array
 * @return int整型
*/
func maxLength( arr []int ) int {
    // write code here
    max := 1
    for i:=0; i< len(arr)-1; i++ {
        exist := make(map[int]int)
        count := 0
        if arr[i] == arr[i+1] {
            continue
        }

        exist[arr[i]] = i
        count += 1
        for j:=i+1; j<len(arr); j++{
            if index, ok := exist[arr[j]]; ok {
                i = index
                break
            }
            exist[arr[j]] = j
            count += 1  
        }
        if count > max {
            max = count
        }

    }
    return max

}

在第一版当中 我们的exist 为map[int]bool, 代码如下：

package main

/**
 * 
 * @param arr int整型一维数组 the array
 * @return int整型
*/
func maxLength( arr []int ) int {
    // write code here
    max := 1
    for i:=0; i< len(arr)-1; i++ {
        exist := make(map[int]bool)
        count := 0
        if arr[i] == arr[i+1] {
            continue
        }

        exist[arr[i]] = i
        count += 1
        for j:=i+1; j<len(arr); j++{
            if _, ok := exist[arr[j]]; ok {

                break
            }
            exist[arr[j]] = true
            count += 1  
        }
        if count > max {
            max = count
        }

    }
    return max

}

这个代码是无记忆的，对于 1232456,第一遍123 遇到2终止；第二遍从2开始，遇到2终止；这里面其实是没必要的，遇到2之后，后续最大的只可能从前一个2的index开始，所以我们直接将i跳转到index，后续的i++，使其指向index+1，从这个地方开始遍历，可以极大的减少搜索次数。