lintcode 384. 最长无重复字符的子串 尺取法

缘起

日常浪费生命~ lintcode 384. 最长无重复字符的子串

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定一个字符串，请找出其中无重复字符的最长子字符串。

样例
样例 1:

输入: "abcabcbb"
输出: 3
解释: 最长子串是 "abc".
样例 2:

输入: "bbbbb"
输出: 1
解释: 最长子串是 "b".
挑战
O(n) 时间复杂度

其实就是【1】的变形而已.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    /**
     * @param s: a string
     * @return: an integer
     */
    int lengthOfLongestSubstring(string &s) {
		memset(v, 0,sizeof(v));
		int len = s.length(), ans = 0;
		for (int i = 0,j=0;i<len; i++)
		{
			v[s[i]]++; // 尺取虫头部进动
			if (v[s[i]]==1) // 满足条件就更新答案
			{
				ans = max(ans, i-j+1);
			}
			else
			{
				while(s[j]!=s[i])
				{
					--v[s[j]];
					j++;
				} // 尺取虫尾部进动直至满足
				v[s[j++]]=1;
			}
		}
		return ans;
    }

	int v[256]; // 表示各种字符出现的次数, 本题比较恶心,没说明字符集,害得我RE了一发
};

ac情况

1
2
3
4
5
Accepted
由 LintCode领扣极速闪测 强力驱动
100%
100% 数据通过测试总耗时 51 ms
您的提交打败了 11.40% 的提交!

参考

【1】