Golang/Java 實現無重複字符的最長子串 – LeetCode 算法
給定一個字符串 s ，請你找出其中不含有重複字符的 最長子串 的長度。
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/longest-substring-without-repeating-characters
示例
示例 1:
輸入: s = "abcacadabcd"
輸出: 4
解釋: 因為無重複字符的最長子串是 "dabc"，所以其長度為 3。
示例 2:
輸入: s = "bbbbb"
輸出: 1
解釋: 因為無重複字符的最長子串是 "b"，所以其長度為 1。
示例 3:
輸入: s = "pwwkew"
輸出: 3
解釋: 因為無重複字符的最長子串是 "wke"，所以其長度為 3。
請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。
示例 4:
輸入: s = ""
輸出: 0
解題思路
原始字符串：abcacadabcd
Golang 代碼實現
func lengthOfLongestSubstring(s string) int {
lastOccurred := make(map[byte]int)
start := 0 // 子串開始的下標
maxLength := 0 // 最大子串長度
for index, ch := range []byte(s) {
// 如果當前字符存在 map 中
//且當前字符的下標在start子串開始位置之後的，如果成立則為發生重複
// 發生重複 start 則當前字符所在的子串下標(map中的下標)後移一位
lastI, ok := lastOccurred[ch]
if ok && lastI >= start {
start = lastI + 1
}
// 計算當前字符下標(index)與 start 下標的距離
distance := index - start + 1
if distance > maxLength {
maxLength = distance
}
// key:當前字符 Ascii 碼，value:當前字符下標
lastOccurred[ch] = index
}
return maxLength
}
Java 代碼實現
class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLen = 0;
int start = 0;
HashMap<Character, Integer> lastOccurred = new HashMap<>();
char[] chars = s.toCharArray();
int charsLen = chars.length;
for (int i = 0; i < charsLen; i++) {
// 從 map 中獲取元素，元素存在且元素出現在start開始的子串中則為重複
Integer lastI = lastOccurred.get(chars[i]);
if (null != lastI && lastI >= start) {
start = lastI + 1;
}
// 計算距離
int distance = i - start + 1;
if (distance > maxLen) {
maxLen = distance;
}
lastOccurred.put(chars[i], i);
}
return maxLen;
}
}
