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

NC41 最长无重复子数组

题意分析：

找出最长的子数组的长度，要求该子数组中没有重复元素。

题解一（暴力）：

找出所有的没有重复元素的子数组，然后比较他们的长度。

超时。

题解二（双指针）：

我们设置两个指针left和right，表示子数组的左端点和右端点，用一个set统计left-right中所有元素。如果left-right里面没有重复元素，就要扩展left-right。right右移。

如果扩展的元素没有出现在set中，那right右移就是可行的，记录此时的长度

如果扩展的元素出现在set中，这时候就需要收缩left，将left右移，直到left-right中间没有重复元素，只要left移动到与right重复元素的下一个位置即可，原有的left-新的right这一段元素删除。

示例如下：

图片说明

重复上面步骤，直到right移动到数组的末尾处。

int maxLength(vector<int> &arr) {
    map<int, int> m;
    int left = 0, right = 0;
    int ret = 0;
    while (right < arr.size()) {
        if (m[arr[right]] == 0) {
            m[arr[right]] = right + 1;
            ret = max(ret, right - left + 1);
        } else {
            //收缩left
            for (; left < m[arr[right]]; left++) {
                m[arr[left]] = 0;
            }
            m[arr[right]] = right + 1;
        }
        right++;
    }
    return ret;
}

map可以替换成其他的数据结构，如set，队列。

时间复杂度： $O(n)$

空间复杂度： $O(n)$