0%

LeetCode No3 Longest Substring Without Repeating Characters

题目

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

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

示例

1
2
Input: s = "abcabcbb"
Output: 3
1
2
Input: s = "bbbbb"
Output: 1
1
2
Input: s = "pwwkew"
Output: 3

思路

如果为空,输出0;否则至少输出1。

进入while循环判断是否满足停止条件,以及对于长度进行保存。

解法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
public int lengthOfLongestSubstring(String s) {
int num = 1, cb = 0, cursor = 0, numres = 0;
//如果s为空,则输出numres=0,否则一定会进入while循环体
//令num是迭代过程中记录目前最长的变量
//cb是当前s的最长字符串的起始位置,cursor是当前最长字符串的末尾
int sL = s.length();
while ((sL - cursor) >= 1) { //如果满足该条件,说明后面到达s的最后一个元素
for (int i = 0; i < cursor-cb; i++) { //i < cursor - cb 即首尾不能在同一个位置
//判断s的cursor位置的元素是否与cb到cursor-1之间有重复,如果在cb+i处有重复,将cb转到cb+i+1处
//解释一个问题:如果在cb+i+2处还有重复怎么办呢?
//这个迭代过程从开始就能能够保证在cb到cursor-1之间没有重复
if (s.charAt(cursor) == s.charAt(cb + i)) {
num=cursor-cb-i; //将num赋值为当前的长度
cb=cb+i+1;
break;
}
}
numres = num > numres ? num : numres;
//numres记录每一次的长度,如果来保证numres永远是代表最长的子串
if (cursor < sL-1) {
//满足条件表明cursor没有到达最后,先预假设不重复,将num+1,再次进入循环判断是否重复
cursor++;
num++;
} else {
break;
}
}
return numres;
}

标准解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int lengthOfLongestSubstring(String s) {
int i = 0, j = 0, max = 0;
Set<Character> set = new HashSet<>();
while (j < s.length()) { //满足条件进入循环体
if (!set.contains(s.charAt(j))) {
//如果set里面没有s在j处的元素,则将其加入set,并且将得到max与set.size()中更大的一个
set.add(s.charAt(j++));
max = Math.max(max, set.size());
} else {
//如果set已经有s在j处的元素,则将前面的元素删除,即相当于cb往后移一位
//如果是i+2处有重复元素,则需要remove 3次
set.remove(s.charAt(i++));
}
}
return max;
}

优缺点

我的循环可能过多,在while里面还有一个for,而且我也没有用到set集合,只是简单的遍历

但是我的while比他少,我可以在for里面直接定位到那一个最确切的元素位置,不需要进行很多次while循环