字符串

字符串算法题

---

leetcode3_无重复字符的最长子串

题目

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。 示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题思路分析

dict / array + 双指针，利用快慢指针，并记录访问过的字符下标。当发现重复字符时，会有该字符出现的下标 + 必须大于慢指针所在下标，则更新慢指针下标。 每次都会更新字符所在下标。

1、哈希辅助-双指针；时间复杂度O(n)，空间复杂度O(1)

func lengthOfLongestSubstring(s string) int {
	m := make(map[uint8]int)
	max, j := 0, 0
	for i := 0; i < len(s); i++ {
		if v, ok := m[s[i]]; ok && v >= j {
			j = v + 1
		} else if i + 1 - j > max {
			max = i + 1 - j
		}
		m[s[i]] = i
	}
	return max
}

2、数组辅助-双指针；时间复杂度O(n)，空间复杂度O(1)

func lengthOfLongestSubstring(s string) int {
    arr := [256]int{}
    for i := range arr {
        arr[i] = -1
    }
    max, j := 0, 0 
    for i := 0; i < len(s); i++ {
        if arr[s[i]] >= j {
            j = arr[s[i]] + 1
        } else if i + 1 - j > max {
            max = i + 1 - j
        }
        arr[s[i]] = i
    }
    return max
}

总结：

Medium题目，考察基本的双指针法解题

---