package NC;

import java.util.*;

/**
 * NC41 最长无重复子数组
 *
 * 给定一个数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
 * 子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
 *
 * 要求：空间复杂度O(n) ，时间复杂度O(logn)
 *
 * @author Tang
 * @date 2021/9/28
 */
public class MaxLength {

    /**
     * 找到以每个元素开头的无重复长度
     * 比较出最大长度
     * （时间复杂度较大，空间复杂度一般）
     *
     * @param arr
     * @return
     */
    public int maxLength (int[] arr) {
        // write code here

        int maxLength = 0;

        Map<Integer, Integer> map = new HashMap<>();

        //每次遍历算出以i开始的连续最长串
        for(int i = 0; i < arr.length; i++) {
            int length = 1;
            map.put(arr[i], i);

            for(int j = i+1; j < arr.length; j++) {
                if(map.containsKey(arr[j])) {
                    break;
                }
                length++;
                map.put(arr[j], j);
            }
            maxLength = Math.max(maxLength, length);
            map.clear();
        }
        return maxLength;

    }


    public static void main(String[] args) {


    }


}