力扣LeatCode算法题第三题-无重复字符的最长子串

要求：

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

我一开始采用的第一种方法是使用hashmap去比对大小，在idea上可以跑通程序，但在leatcode的编译器中，无法通过字符串s="" 和s=" "的校验，很奇怪。

package com.zhm.test;
 
import java.util.HashMap;
import java.util.Map;
 
/**
 * @Author bige
 * @Date: 2022/11/18 8:39
 * @ApiNote: 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 */
public class Leatcode_test003 {
    public static int lengthOfLongestSubstring(String s) {
        //每一道算法题，先想出解题思路。
        //1.判空
        //2.思路想法。
        // 2.1.可以使用hashMap类型
        // 2.2 key作为索引下标0,1,2,3.   每个字母作为value
        // 2.3 循环比对所有的value，返回key. 求出key的差值大小=length。
 
        Map stringHashMap = new HashMap();
        int max = 0;
        String[] split = s.split("");
        for (int i = 0; i < split.length; i++) {
            stringHashMap.put(i,split[i]);
        }
 
        if(split.length<1){
            max=0;
        }else if(split.length==1){
            max=1;
        }else{
            for (Map.Entry entry : stringHashMap.entrySet()) {
                for (int j = entry.getKey()+1; j < split.length; j++) {
                    if(entry.getValue().equals(split[j])){
                        max=(max < (j - entry.getKey()) ) ? (max = (j - entry.getKey())) : max;
                        break;
                    }
                }
            }
        }
    return max;
    }
 
    public static void main(String[] args){
        String s = " ";
        System.out.println("max="+lengthOfLongestSubstring(s));
    }
}

可以在idea中输出正确的结果。

尝试使用下第二种方法去验证。

利用String本身的方法去进行调用和判断，利用indexOf()方法，可以进行返回首次出现的下标。

public static int lengthOfLongestSubstring(String s) {
        int index=0;//索引
        int des=0;//差值
        for (int i = 0; i < s.length(); i++) {
            if(s.indexOf(s.charAt(i),index) < i){
                index=s.indexOf(s.charAt(i),index)+1;
            }else {
                //des=Math.max( des, i - index + 1);
                des=des>(i-index+1)?des :(i-index+1);
            }
        }
        return des;
    }

代码解析：

1.进入if的唯一条件是出现了同样的字母。

例如测试数据：

String s = "abcabcbb";

首次出现：int index=0;

再次出现：int lastIndex =3;

但由于我们使用的IndexOf()方法，再次出现的a字母，会导致索引返回第一次出现字母a的索引index=0。 所以才能进入到if的判断语句中。

if（）方法中，+1的作用是因为每再次遇到相同字母就+1.

比如测试数据：

String s1 = "cacccc";

首次c的索引=0，index=0;

第二次遇到c的索引=2，index=1;

第三次遇到c的索引=3，index=2;

第三次遇到c的索引=4，index=3;

第三次遇到c的索引=5，index=4;

主要是防止重头开始索引，需要移动下标。

贴上所有代码，可以在idea中进行数据测试。

package com.zhm.test;
 
import java.util.HashMap;
import java.util.Map;
 
/**
 * @Author bige
 * @Date: 2022/11/18 8:39
 * @ApiNote: 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 */
public class Leatcode_test003 {
    public static int lengthOfLongestSubstring1(String s) {
        //每一道算法题，先想出解题思路。
        //1.判空
        //2.思路想法。
        // 2.1.可以使用hashMap类型
        // 2.2 key作为索引下标0,1,2,3.   每个字母作为value
        // 2.3 循环比对所有的value，返回key. 求出key的差值大小=length。
 
        Map stringHashMap = new HashMap();
        int max = 0;
        String[] split = s.split("");
        for (int i = 0; i < split.length; i++) {
            stringHashMap.put(i,split[i]);
        }
 
        if(split.length<1){
            max=0;
        }else if(split.length==1){
            max=1;
        }else{
            for (Map.Entry entry : stringHashMap.entrySet()) {
                for (int j = entry.getKey()+1; j < split.length; j++) {
                    if(entry.getValue().equals(split[j])){
                        max=(max < (j - entry.getKey()) ) ? (max = (j - entry.getKey())) : max;
                        break;
                    }
                }
            }
        }
    return max;
    }
 
    public static int lengthOfLongestSubstring(String s) {
        int index=0;//索引
        int des=0;//差值
        for (int i = 0; i < s.length(); i++) {
            if(s.indexOf(s.charAt(i),index) < i){
                index=s.indexOf(s.charAt(i),index)+1;
            }else {
                //des=Math.max( des, i - index + 1);
                des=des>(i-index+1)?des :(i-index+1);
            }
        }
        return des;
    }
 
    public static void main(String[] args){
        String s = "abcabcbb";
        String s1 = "cccccc";
        System.out.println("length="+s.length());
        System.out.println("max="+lengthOfLongestSubstring(s));
    }
}