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

该题目可以使用双指针+哈希表的方式进行求解。
首先针对数组arr来说，我们应该定义一个哈希表hash用来存储arr中出现过的元素以及对应下标。
接下来我们使用双指针法进行求解：定义slow,fast两个指针。

1. fast指针用来遍历arr中出现过的所有元素，作为最长无重复子数组的末尾下标
2. slow用来指向最长无重复子数组的开始下标

之后我们就开始遍历arr数组，总共可以分为两种情况：

1. arr[fast]在哈希表hash中没有出现过，那么此时只需要把arr[fast]和对应的下标fast添加到hash中即可
2. arr[fast]在哈希表hash中出现过,那么此时我们就要修slow的下标，以确保子数组中没有nums[fast]。假设arr[fast]在哈希表中对应的迭代器为pos，那么pos->second就是arr[fast]在arr中出现的下标。不过这个时候我们需要考虑一个问题，那么就是slow只能向后移动，不能向前移动。如果向前移动那么就会包含其他的重复元素，因此就有

最终我们计算子数组长度fast-slow+1，并用一个额外变量进行保存。最终将最长的子数组长度输出即可。

class Solution {
public:
    /**
     *
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        // write code here
        if (arr.size() == 1)
            return 1;
        int maxValue = LONG_MIN;
        int fast = 0, slow = 0,length = 0;
        // hash的key是arr中出现的数字，value是数字对应的下标
        unordered_map<int,int> hash;
        // fast用来遍历arr中所有元素
        // slow用来指向子序列中不重复的元素
        for (; fast < arr.size(); fast++) {
            // 查找arr[fast]在hash中是否存在
            unordered_map<int,int>::iterator pos = hash.find(arr[fast]);
            // 若不存在则将(arr[fast],fast)添加到hash中，并且slow的值不改变
            if (pos == hash.end())        
                hash.insert(make_pair(arr[fast],fast));
            else {
                // 如果存在，则pos->first = arr[fast],那么理论上应该让slow指向pos->first对应下标的下一个值
                // 即 pos->second+1，但是我们应该考虑一下，slow值只能向后移，不能向前移动
                // 往前移动的会造成包含一些重复的元素
                slow = max(pos->second + 1,slow);// 这一步很重要!!!!!
                pos->second = fast;
            }
            length = fast - slow + 1;
            maxValue = max(maxValue, length);
        }
        return maxValue;
    }
};