leetcode刷题笔记--3. Longest Substring Without Repeating Characters

原题链接3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
解题思路:为每一个字符开辟一个hashtable+滑动窗口进行求解,这样更新不重复子串的长度,得到最大值

func lengthOfLongestSubstring(s string) int {
    var posi [256]int
    for i,_ := range posi {
        posi[i] = -1
    }
    curr_len, max_len, start := 0, 0, 0
    for i, v := range s {
        val := int(v)
        if posi[val] == -1 {
            curr_len += 1
        } else {
            if start < posi[val] {
                start = posi[val] 
            }
            curr_len = i - start
        }
        posi[val] = i

        if curr_len > max_len {
            max_len = curr_len
        }
    }
    return max_len
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容