LeetCode-003无重复字符的最长子串(Longest Substring Without Repeating Characters)

LeetCode-003

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


Example

Example 1:

Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2:

Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:

Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.


Solution

class Solution {
public int lengthOfLongestSubstring(String s) {
int cur=0; //Cursor
int len=s.length(); //Length
char str[]=new char[len]; //Array
int letters[]=new int[128]; //Counter
int longest=0; //Longest
int maxLetter=0; //Index of max
int lettersIndex[]=new int[128]; //Index of character
int former=0; //Former position if repeat
int letter=0; //Ascii of letter
for (;cur<len;cur++)
str[cur]=s.charAt(cur);
for (cur=0;cur<len;cur++) {
for (int index=cur;index<len;index++) {
letter=str[index]; //Letter --- str[index]-'A'
lettersIndex[letter]+=index; //Sum of position, to find the former.
if (++letters[letter]==2) { //Repeat!
maxLetter =IntStream //Stream
.range(0,letters.length)
.reduce((i,j)-> //Lambda expression
letters[i]>letters[j]?i:j)
.getAsInt();
former=lettersIndex[letter]-index;
longest=longest>index-cur?longest:index-cur;
cur=former; //cur=former+1, cause 'c++'
break;
}
if (index==len-1) { //No repeat
longest=longest>len-cur?longest:len-cur;
cur=len; //End
break;
}
}
zeros(letters);
zeros(lettersIndex);
}
return longest;
}
public int[] zeros(int[] array) {for (int i=0;i<array.length-1;i++) array[i]=0; return array;}
}

题目描述:
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

总结:

执行用时139 ms,在所有 Java 提交中击败了18.59%的用户。
内存消耗46.8 MB,在所有 Java 提交中击败了65.42%的用户。

字符串定长,Array最高效,但现在跑的效率还是极低的。

记:
已经写过1,2,3,7,9,13,14,20,706九道,在写 Top-100-liked-questions ,账户页面 https://leetcode-cn.com/u/v2beach/ ,尝试在csdn记录,会努力找到每个题的最优解,欢迎互勉和监督。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×