最长无重复子数组

• 模拟滑动窗口 + hash-map

题目描述

给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。 子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

示例

输入：[2,3,4,5]
返回值：4

说明：
[2,3,4,5]是最长子数组

C++实现

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        // write code here
        // 模拟队列 + hash-map
        unordered_set<int> mp;

        int size = arr.size();
        int maxLen = 0;
        int start = 0;
        for (int i = 0; i < size; i++) {
            if (!mp.count(arr[i])) {
                maxLen = max(maxLen, i-start+1);
                mp.insert(arr[i]);
                continue;
            }

            // duplicate
            for (int j = start; j < i; j++) {
                if (arr[j] == arr[i]) {
                    start = j+1;
                    break;
                }
                mp.erase(arr[j]);
            }
        }

        return maxLen;
    }
};

golang实现

package main
//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param arr int整型一维数组 the array
 * @return int整型
*/
func maxLength( arr []int ) int {
    // write code here
    // 模拟窗口 + hash-map
    mp := make(map[int]bool)
    start := 0
    maxLen := 0
    for i, num := range arr {
        if _, ok := mp[num]; !ok {
            maxLen = max(maxLen, i-start+1)
            mp[num] = true
            continue
        }

        // duplicate
        for j := start; j < i; j++ {
            if arr[j] == arr[i] {
                start = j+1
                break
            }
            delete(mp, arr[j])
        }
    }

    return maxLen
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}