3. 无重复字符的 最长子串

1.题目:

image-20200624145409923

2.思路:

3.滑动窗口的概念:

  • 利用 双指针 来实现;即左指针 表示窗口左边界,右指针 表示窗口右边界;
  • 然后滑动,即意味着 有序地,左右指针移动

4.判断重复字符:

5.代码:

法一:用HashSet直接查(里面只存一个值对象)

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
import java.util.*;

public class 无重复字符的最长子串_3 {
public static void main(String[] args) {
}
public int lengthOfLongestSubstring(String s){
//HashSet:记录每个字符是否出现过
Set<Character> occ = new HashSet<Character>();
/*
· set.remove()
· set.add()
· srt.contains()
* */
//对比:
// Map<String, String> map = new HashMap<>();
int rk = -1,ans = 0;//rk:右指针;
int n = s.length();
for(int i = 0; i < n ; i++){
if(i != 0){//左指针右移
occ.remove(s.charAt(i-1));
}
while(rk + 1 < n && !occ.contains(s.charAt(rk+1))){
occ.add(s.charAt(rk+1));
++rk;
}
ans = Math.max(ans, rk - i + 1);//返回最长的长度值;
}
return ans;
}
}

法二:,更简洁的滑动

HashMap(Key, Value)

  • 标签:滑动窗口

  • 暴力解法时间复杂度较高,会达到 O($N^2$)

  • 故而采取滑动窗口的方法降低时间复杂度

  • 定义一个 map 数据结构存储 (k, v),其中 key 值为字符,value 值为字符位置 +1,加 1 表示从字符位置后一个才开始不重复

  • 我们定义不重复子串的开始位置为 start,结束位置为 end

  • 随着 end 不断遍历向后,会遇到与 [start, end] 区间内字符相同的情况,此时将字符作为 key 值,获取其 value 值,并更新 start,此时 [start, end] 区间内不存在重复字符

  • 无论是否更新 start,都会更新其 map 数据结构和结果 ans。

  • 时间复杂度:O(n)

  • public int lengthOfLongestSubstring_滑动窗口(String s){
      int n = s.length(), ans = 0;
      Map<Character, Integer> map = new HashMap<>();
      for(int end=0,start=0; end<n; end++){
        char alpha = s.charAt(end);
        if(map.containsKey(alpha)){
          start = Math.max(map.get(alpha), start);//这个很重要
        }
        /*
        * if(map.containsKey(s.charAt(i)))
        * j = Math.max(map.get(s.charAt(i)),j);
        * 为什么有这个判断,是因为在滑动过程中会出现当前loop出现的重复元素之间的区间,
        * 可能还有其他元素也是重复的。
        * 如果仅仅 j =map.get(s.charAt(i)) 
        * 则你会忽略两个重复元素之间还有的其他元素也是重复的,
        * 例如 a bba ,如果没有max,则答案会是3,因为最后一个a和前一个a的间距是3,
        * 不加max就考虑不到中间两个b也是重复的。)
        * */
        ans = Math.max(ans, end - start + 1);
        map.put(s.charAt(end), end+1);
      }
      return ans;
    }
    <!--1-->
  • 返回从 fromIndex 位置开始查找指定字符在字符串中第一次出现处的索引,如果此字符串中没有这样的字符,则返回 -1。

  • int indexOf(String str);
    <!--2-->
    
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
class Solution {
public int lengthOfLongestSubstring(String s) {
int i = 0;
int flag = 0;
int length = 0;
int result = 0;
while (i < s.length()) {
int pos = s.indexOf(s.charAt(i),flag);
if (pos < i) {
if (length > result) {
result = length;
}
if (result >= s.length() - pos - 1) {
return result;
}
length = i - pos - 1;
flag = pos + 1;
}
length++;
i++;
}
return length;
}
}

作者:VioletKiss
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/javati-jie-3wu-zhong-fu-zi-fu-de-zui-chang-zi-chua/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。