剑指offer 最长不重复子串

mb,错了一天,D了一天bug,真爽。脑子秀逗的感觉。


func lengthOfLongestSubstring(s string) int {
	var start,end = 0,0
	var max = 0
	var hashMap = make(map[byte]int,100)
	//hashMap[s[0]] = 0
	//t,ok := hashMap[s[end+1]]
	for ;end<len(s);{
		t,ok := hashMap[s[end]]
		if ok && t>=start{                      //这里之前没有判断t,导致在map中,start之前位置可能有重复字符,导致失败。
			if max < end-start{
				max = end-start
			}
			start = hashMap[s[end]]+1
		}else {
			hashMap[s[end]] = end
			end++
		}

	}
	if max < end-start{               //如果整个字符串一个重复字符没有,那么end = lenl(s)直接退出,不会执行循环里的长度判断
		max = end-start
	}
	return max
}



又写了一个切片的
func lengthOfLongestSubstring(s string) int {
	var max = 0
	var locations = [128]int{0}
	for i:= 0; i < len(s); i++{ //切片下标为字母,所以一开始没设置为-1时,下面读的locations可能为0,等于了start,但实际第一个元素还没有存入
		locations[s[i]] = -1
	}
	n := len(s)
	var start,end = 0,0
	for ;end<len(s);end++{
		if locations[s[end]] >= start{
			start = locations[s[end]]+1
		}
		if end-start+1> max{
			max = end - start +1
			if max >= n-start{
				break
			}
		}
		locations[s[end]] = end
	}
	return max
}


发表评论 / Comment

用心评论~