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

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {

        if (arr == null || arr.length == 0) {
            return 0;
        }

       /**
         * 思路:
         * 如:[1,2,3,4,5,6,7,8,1,11,12,13,14] startIndex =0 当遍历到数组第8个位置1的时候,
         * 此时应从第一次出现重复元素0的位置元素1的下一个位置[2,3,4,5,6,7,8,1,11,12,13,14]
         */
        /**
         * hash数组长度为10的5次方,因为题中1≤n≤10的5次方 hash数组Index 0-99999 初始化中每个元素初始值为0
         */
        int[] hash = new int [100000];

        int startIndex = 0;

        int maxLen = 1;

        for (int i = 0; i < arr.length; i++) {

            int curVal = arr[i];

            /**
             * 如果没有不重复元素,hash[currentArrayVal]这个值就一直是0,那么start不会改变
             * 如果出现重复元素,就会取重复元素的索引的位置的值,作为索引值
             */
            startIndex = Math.max(startIndex, hash[curVal]);

            /**
             * 有重复元素情况下:在hash数组中存的是重复元素在数组中元素的下一个坐标 如:
             * [1,2,3,4,5,6,7,8,1,11,12,13,14] startIndex =0 当遍历到数组第8个位置1的时候
             * hash[curVal] = 1 代表此时应从第一次出现重复元素0的位置元素1的下一个位置[2,3,4,5,6,7,8,1,11,12,13,14]
             * 那么在之前一个元素8的时候 i=7 hash[curVal] = 0(因为没重复元素 所以hash中一直是0)
             * 数组下标-1=7 应+1 代表[1,2,3,4,5,6,7,8]的8的长度
             */
            maxLen = Math.max(maxLen, i-startIndex+1);

            hash[curVal] = i + 1;
        }

        return maxLen;
    }
}