3.无重复字符的最长子串

题目描述

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

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例2：

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例3：

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

思路

1.将字符串中的每个字符都放入一个哈希表中，方便滑动窗口。
2.设置最大值ans，用于表示最长子串；设置start，用于表示窗口的起始坐标；设置end，用于表示窗口的截止坐标。
3.遍历整个字符串中的字符，当遍历到字符串的某一个字符时，检查该字符是否存在于哈希表中。若存在，则重置start的位置；若不存在，则将该字符作为键值放入哈希表中。

Java代码实现

public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        Map<Character,Integer> indexMap = new HashMap<>();
        for(int start=0,end=0;end<s.length();end++){
            char c = s.charAt(end);
            if(indexMap.containsKey(c)){
                start = Math.max(indexMap.get(c)+1,start);
            }
            ans = Math.max(ans,end-start+1);
            indexMap.put(c,end);
        }
        return ans;
    }

Golang代码实现

func lengthOfLongestSubstring(s string) int {
    left := 0
    strMap := make(map[byte]int)
    res := 0

    for i:=0;i<len(s);i++{
        cur := s[i]
        if index,ok := strMap[cur]; ok{
            left = max(left,index+1)
        }
        strMap[cur] = i
        res = max(res,i-left+1)
    }
    return res
}

func max(a int,b int) int{
    if a>b {
        return a
    }else{
        return b        
    }