当前位置: 代码迷 >> 综合 >> 明明的leetcode日常:3. Longest Substring Without Repeating Characters
  详细解决方案

明明的leetcode日常:3. Longest Substring Without Repeating Characters

热度:95   发布时间:2024-01-10 00:31:32.0

题目:
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.

今天依然是不用VS写代码的一天,在网页上写代码一遍过,真实喜大普奔。
我希望能够达到O(n)的时间复杂度,因此我采取的策略是:设计一个数组存放当前子字符串中字符在string中的位置。数组的下标是当前字符的ASCII码,数组中的元素是该字符在string中的位置。从头开始逐个字符地遍历string,如果在数组中没有查找到这个字符,也就是说数组中该字符指示的位置是0,就表示当前截取的子字符串没有包含这个字符,反之就表示这个字符已经包含在子字符串里了,那么子字符串如果想要吃进这个字符,就要把以前出现过的这个字符以及它之前的所有字符都删掉。
我的思路和其他人给出的答案大致相同,但是我的代码还不够简洁。

class Solution {
public:int lengthOfLongestSubstring(string s) {int longest_length=0;int now_length=0;int start_point=0;int char2place[257]={
   0};for(int id=0;id<s.size();++id){int character = int(s[id]);if(char2place[character]){for(int j=start_point;j<char2place[character];++j){int delete_char=int(s[j]);char2place[delete_char]=0;--now_length;++start_point;}}char2place[character]=id+1;++now_length;if(now_length>longest_length) longest_length=now_length;}return longest_length;}
};
  相关解决方案