碧海长天

好看的皮囊千篇一律,有趣的灵魂万里挑一。

leetcode刷题心得:003 无重复字符的最长子串

2020-4-5

很久前第一次做这道题,觉得平平无奇,没什么可记录的。今日二刷,发现了一个比较有意思的解法。抄过来~

题目地址:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

思路:因为从字符串中获取到每个元素,都是一个ASSCI值。从0-127种内容。所以用一个长度为128的数组来记录每种字符“上次”出现的位置。 (好好理解一下“上次”)
然后,遍历每一个字符时,都算一个最新的不重复的长度。然后把该长度和历史最大出现的长度做比较。 谁长,就谁的值。
见代码: 其中i记录的是上次出现当前元素时的位置。

func lengthOfLongestSubstring(s string) int {
        val := []byte(s)
	kvMap := make([]int, 128)
	lens := len(s)
	var max, num int
	for i, j := 0, 0; i < lens && j < lens; j++ {
		if kvMap[val[j]] > i {
			i = kvMap[val[j]]
		}
		num = j - i + 1
		if num > max {
			max = num
		}
		kvMap[val[j]] = j + 1
	}
	return max
}

其实,就算如此,这也只能算是一个普通的题目。但是我有另一个小发现。
kvMap := make([]int, 128)
这行,如果换成
kvMap := make(map[byte]int,len(s))
效果会怎样?经过耗时对比,kvMap 如果用数组,性能比用map性能高数倍。
这就牵扯到数组、map两种数据类型,在golang中的实现了。
显而易见,只讨论根据特定key读取的话,数组的性能是远超map的。
因此,以后的算法题,如果想减少耗时。巧妙的利用数组,也可以作为一种思路。

发表评论: