题目

给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。

解题思路

第一步把暴力重复遍历字符串的方式去掉。
定义不重复的字符的起始变量left=0,遍历字符串放入到map,key为单个字符,value为字符在String中的位置+1,获取当前最大长度ans=max(ans,当前字符串位置-left),如果key存在,则获取最新的left=max(map.get(key),left)。

show code

public static int getLength(String s) {
    int n = s.length(), ans = 0;
    Map<Character, Integer> map = new HashMap<>();
    for (int right = 0, left = 0; right < n; right++) {
        char value = s.charAt(right);

        //获取目前为止最后重复字符的标志位
        if (map.containsKey(value)) {
            left = Math.max(map.get(value), left);  
        }
        ans = Math.max(ans, right + 1 - left);
        map.put(value, right + 1);
    }
    return ans;
}

加戏

上面只是列出了长度,如果要列出字符串和起止位置呢?

解题思路

定义起止坐标,当 当前ans小于Math.max(ans, right + 1 - left)的时候,则更新起止坐标。

show code

public static String getStr(String s){
    int n = s.length(), ans = 0,index_start = 0,index_end=0;
    Map<Character, Integer> map = new HashMap<>();
    for (int right = 0, left = 0; right < n; right++) {
        char value = s.charAt(right);

        //获取目前为止最后重复字符的标志位
        if (map.containsKey(value)) {
            left = Math.max(map.get(value), left);  
        }

        //ans是从0开始的,所以即使一直没有重复的字符,index_end也是一直增加的,index_start则不会变化
        if(ans<=right + 1 - left) {
            index_end = right+1;
            index_start = left+1;
        }
        ans = Math.max(ans, right + 1 - left);
        map.put(value, right + 1);
    }
    System.out.print(ans+"-"+index_start+"-"+index_end+"-");
    return s.substring(index_end-ans, index_end);
}

输入

System.out.println(getStr("abcdbefghicjkbbbbbb"));
System.out.println(getStr("abcdbefghijk"));
System.out.println(getStr("abcdefg"));

输出

10-4-13-dbefghicjk
10-3-12-cdbefghijk
7-1-7-abcdefg

发表评论

电子邮件地址不会被公开。 必填项已用*标注