3.无重复字符的最长子串
题目描述
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例2:
输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例3:
输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
思路
1.将字符串中的每个字符都放入一个哈希表中,方便滑动窗口。
2.设置最大值ans,用于表示最长子串;设置start,用于表示窗口的起始坐标;设置end,用于表示窗口的截止坐标。
3.遍历整个字符串中的字符,当遍历到字符串的某一个字符时,检查该字符是否存在于哈希表中。若存在,则重置start的位置;若不存在,则将该字符作为键值放入哈希表中。
Java代码实现
public int lengthOfLongestSubstring(String s) { int ans = 0; Map<Character,Integer> indexMap = new HashMap<>(); for(int start=0,end=0;end<s.length();end++){ char c = s.charAt(end); if(indexMap.containsKey(c)){ start = Math.max(indexMap.get(c)+1,start); } ans = Math.max(ans,end-start+1); indexMap.put(c,end); } return ans; }
Golang代码实现
func lengthOfLongestSubstring(s string) int { left := 0 strMap := make(map[byte]int) res := 0 for i:=0;i<len(s);i++{ cur := s[i] if index,ok := strMap[cur]; ok{ left = max(left,index+1) } strMap[cur] = i res = max(res,i-left+1) } return res } func max(a int,b int) int{ if a>b { return a }else{ return b }