继续做把第三题的解题思路放上来。第三题的目的是求字符串内最长的不重复子串,两个要求非常清晰。下面是题目的描述:

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", 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.

思路:

假设子串的初始下标为 i,结束下标为 j。i 和 j 的初始值均为 0。j 开始一次往后遍历,如果这个字符串没有重复字符,那么 j 会一直走到最后,此时最长子串就是字符串本身。实际情况没有那么理想,我们主要分析这类场景。当处于 j 位置的字符和子串之前的字符重复(假设位置为 k),那么就应该停下,并且更新最长子串的长度(假设最长长度为 max),j 继续往后走,同时 i 的位置需要挪到重复字符之后,即 k+1 处。直到遍历到字符串的最后。

比如用第一个例子作为说明,初始状态 i = j = 0,最长子串长度 max = 0:

  1. j=0 处的字符是 a,无重复,当前子串长度为 1;
  2. j=1 处的字符是 b,无重复,当前子串长度为 2;
  3. j=2 处的字符是 b,无重复,当前子串长度为 3;
  4. j=3 处的字符是 a,发现重复,更新 max = 3,i = 0+1,当前子串长度为 3;
  5. j=4 处的字符是 b,发现重复,max 不变,i = 1+1,当前子串长度为 3;
  6. j=5 处的字符是 c,发现重复,max 不变,i = 2+1,当前子串长度为 3;
  7. j=6 处的字符是 b,发现重复,max 不变,i = 4+1,当前子串长度为 2;
  8. j=7 处的字符是 b,发现重复,max 不变,i = 6+1,当前子串长度为 1;

因此,"abcabcbb" 的最长子串长度是 3。

接下来我们写上代码:

func lengthOfLongestSubstring(s string) int {
	n := len(s)

	if n <= 1 {
		return n
	}

	tbl := make(map[byte]int, n)
	lo, longest, curr := 0, 0, 0

	for hi := 0; hi < n; hi++ {
		if k, ok := tbl[s[hi]]; ok && k >= lo {
			lo = k + 1
		}

		tbl[s[hi]] = hi
		curr = hi - lo + 1

		if curr > longest {
			longest = curr
		}
	}

	return longest
}

完整的代码参见这里,以及测试代码

转载请注明转自: 团子的小窝 , 本文固定链接: Leetcode 3. Longest Substring Without Repeating Characters

  1. 笑八达's avatar
    笑八达 发表于 1 周前 回复 #1

    感受学习的力量!