LeetCode_3: Longest Substring Without Repeating Characters

# 引言

题目链接：https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

# 题目大意

输入一个字符串，输出没有重复字符的最长子串的长度。

例：

• Example1

Input: "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

• Example2

Input: "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

# 题解

# 一句话题解

利用 map 或者 hash 表映射字符和字符上一次出现的位置，当遇到重复字符时 (当前符合条件子串结束), 查找下一个不包含重复字符的子串起点，同时把当前子串的长度和已有最大值比对记录

• 详解

映射关系中，保存当前字符在字符串已查询部分中最后出现的下标位置 (默认 -1 , 没有出现过)

1. 默认第一个子串起点下标为 0
2. 最大值为当前下标和起点下标的差值与存储的最大值的较大者
3. 当查询到当前字符已经出现过，分两种情况讨论
   • 当前子串的起点下标 > 当前查询字符上一次出现下标位置 (证明当前查询字符在当前子串未出现过，如 tmmzuxt , 查询最后一个 t 当前子串起点为第二个 m )
   • 当前子串的起点下标 <= 当前查询字符上一次出现下标位置 (证明当前查询字符在当前子串已经出现过一次，当前字符串终结，如 wkew , 查询最后一个 w 当前子串起点为第一个 w )

综上所述，情况一当前子串起点位置大于查询字符上一次出现位置，字符在子串第一次出现，保持起点不变即可，情况二当前子串起点位置小于查询字符第一次出现位置，字符在子串第二次出现，当前子串终结，下一个子串起点重置为当前查询字符出现的下一个下标

即 lastDiffIndex = lastDiffIndex > index + 1 ? lastDiffIndex : index + 1;

复杂度 O(n)

# AC 代码

c++ 版本

class Solution

{

  public:

    int lengthOfLongestSubstring(string s)

    {

        int maxn = 0;

        int lastDiffIndex = 0;

        int indexHash[256];

        memset(indexHash, -1, sizeof(indexHash));

        for (int i = 0; i < s.length(); ++i)

        {

            int index = indexHash[s[i] - '\0'];

            if (-1 != index)

            {

                lastDiffIndex = lastDiffIndex > index + 1 ? lastDiffIndex : index + 1;

            }

            indexHash[s[i] - '\0'] = i;

            maxn = maxn > i - lastDiffIndex + 1 ? maxn : i - lastDiffIndex + 1;

        }

        return maxn;

    }

};

go 版本

func lengthOfLongestSubstring(s string) int {

	var maxn, lastDiffIndex int

	indexMap := make(map[int32]int)

	for i, ch := range s {

		index, ok := indexMap[ch]

		if ok {

			if index+1 > lastDiffIndex {

				lastDiffIndex = index + 1

			}

		}

		indexMap[ch] = i

		if i-lastDiffIndex+1 > maxn {

			maxn = i - lastDiffIndex + 1

		}

	}

	return maxn

}