题解 | #最长无重复子串#

看了很多解题都需要用到map，我这里提供一个不需要用到map的解法，使用的时间和内存都比使用map的较小
使用双指针，滑动窗口等概念，类似与leetcode的无重复字符的最长字串解法

import java.util.*;

public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength(int[] arr) {
        // write code here
        // 双指针（左：left，右：right），滑动的窗口（left到right）确保无重复元素
        int left = 0;    // 左指针
        int right = 0;    // 右指针
        int max = 0;    // 保存最大长度  
        while (right < arr.length) {    // 这里使用while循环，也可以使用for遍历
            left = findLeft(arr, left, right);    // 调整滑动窗口，并重置左指针
            max = Math.max(max, right - left + 1);    // 更新最大长度
            right++;
        }
        return max;
    }

    /*调整滑动窗口：对比从left到right的新窗口中是否有与arr[right]重复元素，
    如果有，则从与arr[right]的值重复的元素的下一个元素作为滑动窗口的左指针left*/
    public int findLeft(int[] arr, int left, int right) {
        for (int i = left; i < right; i++) {    // 这里注意不能i <= right，因为当i=right时，arr[i]必然等于arr[right]，返回的left指针就不正确了
            if (arr[right] == arr[i]) return i + 1;    // 如果在对比的范围内出现与arr[right]重复的元素，则从重复元素的下一个开始设置为新的左指针left
        }
        return left;    // 一圈对比下来都没有重复，则左指针left位置不变
    }
}