LeetCode刷题之lengthOfLongestSubstring无重复最长子串Go语言版

题目描述

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

示例

示例一

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

示例二

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

示例三

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

前提约束

• 0 <= s.length <= 5 * 10^4
• s 由英文字母、数字、符号和空格组成

单元测试

还是一样，先编写测试用例

package lengthOfLongestSubstring

import (
    "testing"
)

func TestLengthOfLongestSubstring(t *testing.T) {
    tests := []struct{
        name     string
        s         string
        r         int
        wantErr bool
    }{
        {
            "abcabcbb*3",
            "abcabcbb",
            3,
            false,
        },
        {
            "bbbbb*1",
            "bbbbb",
            1,
            false,
        },
        {
            "pwwkew*3",
            "pwwkew",
            3,
            false,
        },
        {
            "au*2",
            "au",
            2,
            false,
        },
    }

    for _, tt := range tests{
        t.Run(tt.name, func(t *testing.T) {
            x := LengthOfLongestSubstring(tt.s)
            if x != tt.r{
                t.Errorf("结果不符合预期，want:%d, got:%d", tt.r, x)
            }
        })
    }
}

解决方案

package lengthOfLongestSubstring

func LengthOfLongestSubstring(s string) int {
    if len(s) == 0 || len(s) == 1 {
        return len(s)
    }
    length := 0
    n := len(s)
    for i:=0; i < n; i++{
        hmap := make(map[byte]int)
        hmap[s[i]] = i
        for j := i + 1; j < n; j++ {
            if _, ok := hmap[s[j]]; ok {
                //fmt.Printf("find it :%v\n", arr[j])
                break
            } else {
                hmap[s[j]] = j
                //fmt.Printf("insert into:hmap[%v]=%d\n", arr[j], j)
            }
            //fmt.Printf("size of hmap:%d\n", len(hmap))

        }
        if len(hmap) > length {
            length = len(hmap)
        }
    }
    return length
}

初次尝试的解决方案并不理想，执行耗时和内存占用都排名靠后。

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。