leetcode - 无重复字符的最长子串

问题：无重复字符的最长子串

难度: 中等

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

示例 ：

输入: "abcabcbb"
输出: 3  //无重复字符的最长子串是 "abc"

链接：原题链接

解法

解法一：暴力求解

思路：使用 start, length 记录当前子串的起始位置和和子串长度，使用 longest 记录当前的最长子串长度。如果遇到相同的字符，变更搜索起始位置（即 start = i +1）

func lengthOfLongestSubstring(s string) int {
	if len(s) == 0 {
		return 0
	}

	// 如果出现相同的字符，且不是同一个元素，则修改起始的搜索位置，同时比较当前的子串的长度与 longest 的大小
	var start, length,longest = 0, 0, 0
	for sIndex, sValue := range s {
		for i := start; i <= sIndex; i++ {
			length = i - start + 1
			if string(s[i]) == string(sValue) && i != sIndex {
				start = i +1
				if length > longest {
					longest = length
				}
			}else {
				if length > longest {
					longest = length
				}
			}
		}
	}
	return longest
}

时间复杂度：O(N^2)
空间复杂度：O(N)

解法二：使用 map

思路：使用 map (其中 key 存放元素，value 存放 key 在 s 中最后出现的位置)。遍历 s 过程中，如果遇到相同元素，通过判断他们索引的差值，来更新 longest

func lengthOfLongestSubstring1(s string) int {
	if len(s) == 0 {
		return 0
	}
	//记录元素的最后出现位置
	itemLastIndex := make(map[rune]int)
	start := 0
	maxLen := 0
	for index, item := range []rune(s) {
		if lastIndex, ok := itemLastIndex[item]; ok && lastIndex >= start {
			//获取元素上一次出现的位置
			start = lastIndex + 1
		}
		//本次出现位置-上次出现位置
		if index-start+1 > maxLen {
			maxLen = index - start + 1
		}
		itemLastIndex[item] = index
	}
	return maxLen
}

时间复杂度：O(N)
空间复杂度：O(N)