发表更新代码能力 / leetcode2 分钟读完 (大约344个字)

003.Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

  • 建立一个256位的整型数组来记录所有字符；
  • 定义两个变量res和left， res 用来记录最长无重复子串的长度， left 指向该无重复子串左边的起始位置，
  • 遍历整个字符串，对于每一个遍历到的字符，如果哈希表中该字符串对应的值为0，说明没有遇到过该字符。则此时计算最长无重复子串，i - left + 1。其中ｉ是最长无重复子串最右边的位置，left是最左边的位置。
  • 如果该点遇到过，那么更新left的位置。
  • 每次循环中，都要把当前字符对应的值赋值为 i + 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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		int m[256] = { 0 }, res = 0, left = 0;
		for (int i = 0; i < s.size(); ++i) {
			if (m[s[i]] == 0 || m[s[i]] < left) { //元素虽重复，但是出现在最左边的左边
				res = max(res, i - left + 1);
			}
			else {
				left = m[s[i]];
			}
			m[s[i]] = i + 1;//第几位
		}
		return res;
	}
};

int main() {
	Solution test;
	cout << test.lengthOfLongestSubstring("abbca");
	return 0;
}

分类

×