目录

找到字符串的最长无重复字符子串

题目描述

示例1

输入

返回值

示例2

输入

返回值

备注：

方法一：暴力搜索

方法二：链表

方法三：Hashmap

方法四

找到字符串的最长无重复字符子串

题目描述

给定一个数组arr，返回arr的最长无的重复子串的长度（无重复指的是所有数字都不相同）。

示例1

输入

[2,3,4,5]

返回值

4

示例2

输入

[2,2,3,4,3]

返回值

3

备注：

方法一：暴力搜索

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        if(arr.length==1) return 1;
        int maxlen=1;
        for (int i = 0; i < arr.length; i++) {
            HashMap<Integer,Integer> map=new HashMap();
            map.put(arr[i],i);
            int len=1;
            for (int j = i+1; j < arr.length; j++) {
                if(map.containsKey(arr[j])){
                    maxlen=Math.max(maxlen,len);
                    break;
                }else{
                    map.put(arr[j],j);
                    len++;
                }
            }
        }
        return maxlen;
    }
}

 时间消耗确实很慢，

方法二：链表

用LinkedList的removeFirst()调整list的长度并记录

例如：{2,3,4,3}遇到重复元素，remove之后是{4,3}

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        LinkedList<Integer> list = new LinkedList<>();
        int p=0, ans=0;
        for(int i=0;i<arr.length;i++){
            if(list.contains(arr[i])){
                int j=list.indexOf(arr[i]);
                while (j-->=0){
                    list.removeFirst();
                }
            }
            list.add(arr[i]);
            ans=Math.max(ans,list.size());
        }
        return ans;
    }
}

时间和空间消耗都得到了较大的改善，

方法三：Hashmap

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        HashMap<Integer,Integer> map = new HashMap<>();
        int max = 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);
            }
            max = Math.max(max , end-start+1);
            map.put(arr[end],end);
        }
        return max;
    }
}

方法四

该方法最快

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        int[] lastPos = new int[100005];
        int len = arr.length;
        int start = 0;
        int res = 0;
        for(int i =0;i<len;i++){
            int now = arr[i];
            start = Math.max(start,lastPos[now]);
            res = Math.max(res,i-start+1);
            lastPos[now] = i+1;
        }
          
        return res;
    }
}