提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  .Net

当前栏目

最长无重复子串

2023-02-18 16:36:16 时间

题目：

 

 

 

思路：

首先明确了这个可以在一次循环中解决即时间复杂度为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;
    }
}
 

相关文章