最长无重复子串

题目：

思路：

首先明确了这个可以在一次循环中解决即时间复杂度为O（n）

其次，在循环中，我们应能知道起始的位置，然后终止于哪个位置，当碰到终止的时候必然是元素为已经纳入我们统计中的元素。然后我们要如何确认这个元素在哪个位置，并且把一些废弃的元素丢弃掉，重新到下一次统计，直至目标数组遍历完全。

所以我们是否能用一个容器将元素不断纳入，在纳入过程中判断这个元素是否已经被纳入了进来，最好是有序的方便我们吧从某处的元素之前的那些一次性全部丢弃。

方案1结果

方案2结果

方案3结果

代码示例：

import java.util.ArrayList;

import java.util.HashMap;

public class Solution4 {

    public static void main(String[] args) {

        int[] num = {2, 2, 3, 4, 3, 2, 1, 5, 6, 1, 2, 3, 4, 5, 6};

        System.out.println(maxLength1(num));

    }

    /**

     * 方案二

     * 原理：

     * 当某个数在之前出现过，这个时候就把子串的起点start往后推一个，但是有一种情况，

     * 比如1，2，3，4，3，5，1。到第二个3时，以后的子串起点start为4，

     * 到第二个1时，如果不取最大的start，按start = map.get(arr[end])+1

     * 算出起点start为2，显然以起点start=2，结尾end=1的子串234351有重复的，

     * 因此start要取最大的

     * 优点：对于方案一，少了一些对于list的截取与搜索的步骤，相对儿研会少一点操作，应该会节约点时间

     *

     * @param arr int整型一维数组 the array

     * @return int整型

     */

    public int maxLength2(int[] arr) {

        if (arr.length < 2)

            return arr.length;

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

        int res = 1;

        for (int start = 0, end = 0; end < arr.length; end++) {

            if (map.containsKey(arr[end])) {

                start = Math.max(start, map.get(arr[end]) + 1);

            }

            res = Math.max(res, end - start + 1);

            map.put(arr[end], end);

        }

        return res;

    }

    /**

     * 方案三

     * 原理：等同于方案三

     * 优点：对于方案三，直接就建立出极限大小的空间，不用像哈希表那种不断增加空间，其次int数组空间的花费会比HashMap要少（同等长度下）

     * 其次直接读取比用哈希那种内置的检索会快很多，同样是减少操作来达到缩短时间

     *

     * @param arr int整型一维数组 the array

     * @return int整型

     */

    public static int maxLength3(int[] arr) {

        if (arr.length < 2)

            return arr.length;

        int[] last = new int[100000];

        int start = 0;

        int maxLength = 0;

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

            int index = arr[i];

            start = Math.max(start, last[index]);

            maxLength = Math.max(maxLength, i - start + 1);

            last[index] = i + 1;

        }

        return maxLength;

    }

    /**

     * 方案一

     * 原理：

     * 常规方法

     * 把得到的每一个元素塞进一个有序的结构里面

     * 如[1,2,3,4,5],这时候长度为5，如果下一个数是3，

     * 那么最大长度依旧是5，但是数据结构里面的[1,2,3]应当被清除，

     * 因为他们不能用于后续统计中，所以生成新的数据结构[4,5,3]

     *

     * @param arr int整型一维数组 the array

     * @return int整型

     */

    public static int maxLength1(int[] arr) {

        if (arr.length < 2)

            return arr.length;

        int result = 0;

        ArrayList<Integer> list = new ArrayList<Integer>();

        for (int number : arr) {

            if (list.contains(number)) {

                //subList的截取不包含最后一位，但是我们的最后一位也在清除计划内故要加一

                list.subList(0, list.indexOf(number) + 1).clear();

            }

            list.add(number);

            if (list.size() > result) {

                result = list.size();

            }

        }

        return result;

    }

}