-
Notifications
You must be signed in to change notification settings - Fork 0
/
3.无重复字符的最长子串.go
90 lines (87 loc) · 1.64 KB
/
3.无重复字符的最长子串.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*
* @lc app=leetcode.cn id=3 lang=golang
*
* [3] 无重复字符的最长子串
*
* https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
*
* algorithms
* Medium (39.10%)
* Likes: 8793
* Dislikes: 0
* Total Accepted: 2.2M
* Total Submissions: 5.6M
* Testcase Example: '"abcabcbb"'
*
* 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
*
*
*
* 示例 1:
*
*
* 输入: s = "abcabcbb"
* 输出: 3
* 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
*
*
* 示例 2:
*
*
* 输入: s = "bbbbb"
* 输出: 1
* 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
*
*
* 示例 3:
*
*
* 输入: s = "pwwkew"
* 输出: 3
* 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
* 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
*
*
*
*
* 提示:
*
*
* 0 <= s.length <= 5 * 10^4
* s 由英文字母、数字、符号和空格组成
*
*
*/
// @lc code=start
func lengthOfLongestSubstring(s string) int {
ans, dict := 0, [128]int{}
for i, j := 0, 0; j < len(s); j++ {
if i < dict[s[j]] {
i = dict[s[j]]
}
dict[s[j]] = j + 1
if ans < j-i+1 {
ans = j - i + 1
}
}
return ans
}
// @lc code=end
/*
* other top voted solution
*/
func lengthOfLongestSubstring(s string) int {
ans, dict := 0, [128]bool{}
for i, j := 0, 0; j < len(s); j++ {
if dict[s[j]] {
for ; dict[s[j]]; i++ {
dict[s[i]] = false
}
}
dict[s[j]] = true
if ans < j-i+1 {
ans = j - i + 1
}
}
return ans
}