准备

动态规划

实践

字符串 “abcabcbb”

根据索引有如下关系

a b c a b c b b
0 1 2 3 4 5 6 7
  1. \(f(0,1)=f(0,0) + 1\)
  2. \(f(0,2)=f(0,1) + 2\)

在所有字符都不重复的情况下有如下公式

\(f(s,e)=f(s,e-1) + e\)

若遇到重复的情况则，3 索引于当前字串 的 0 重复则表明当前字串已经到头，需要记录并偏移 s，s=1：

  1. \(f(1,3)=f(1,2)+3\)

假设：

  • s - 开始字符索引
  • e - 结束字符索引

若遇到当前字符于前面 r 字符重复则： \[ f(r,e)=f(s,e - 1) + e; s=r \]

解法

func lengthOfLongestSubstring(s string) int {
	if len(s) == 0 {
		return 0
	}
	appearedIndexes := [256]int{}
	for i := 0; i < 256; i++{
		appearedIndexes[i] = -1
	}
	longest, start, end := 0, 0, 0

	b := []byte(s)

	for cIndex, c := range b {
		index := int(c)
		appearedIndex := appearedIndexes[index]
		end = cIndex
		// 出现过需要截断
		if appearedIndex != -1 {
			// 重置已出现的字符
			for i := start; i <= appearedIndex; i++{
				appearedIndexes[b[i]] = -1
			}
			length := end - start
			if length > longest {
				longest = length
			}
			start = appearedIndex+1
		}
		appearedIndexes[index] = cIndex
	}

	if end - start + 1 > longest {
		longest = end - start + 1
	}

	return longest
}