leetcode003无重复字符的最长子串

leetcode003无重复字符的最长子串

二月 20, 2020

leetcode003无重复字符的最长子串-我自己的理解

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

示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

做出来很容易，直接两个for暴力就能解决。但是有更快的方法。假设i为左窗口，j为右窗口。假设Sj’与窗口内的某个值Si重复了，那么这个时候把i+1作为左窗口，继续操作。
下面注释的地方是我理解解题思路后，自己写的过程，发现是一个坑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int lengthOfLongestSubstring(String s) {
    	int max=0,result=0;
    	int[]index=new int[128];
    	for(int i=0;i<index.length;i++)
    		index[i]=-1;
    	for(int i=0,j=0;j<s.length();j++) {
		//abba最后一次循环会让i=1也就是第一个a的后面
		//所以找寻i的方法不对，应该是index[charAt(j)]和上一次的i的较大者
    		
//    		if(index[s.charAt(j)]!=-1) {
//    			i=index[s.charAt(j)]+1;
//    		}
    		i=Math.max(index[s.charAt(j)]+1,i);//第二个参数是上一次的i,所以不会有i+1
    		max=j-i+1;
    		result=Math.max(max, result);
    		index[s.charAt(j)]=j;
    	}
    	return result;
    }

这道题我看了解题思路我还是花了两个小时去写出时间复杂度低答案，思考的过程真累啊，还好最后是弄明白了。在这先立个flag，leetcode 1/100。

两天后的补充。

两天后我再看这道题发现还是有点难算，难点在于i=Math.max那一行，还是没想出来。但是我想出来了比较相近的一种算法，这次不会再让左窗口跳跃，而是一个一个的加，直到右窗口对应的值不在窗口里面。5ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int lengthOfLongestSubstring(String s) {
	     int result=0;
	     int[] index=new int[128];
	     Arrays.fill(index, -1); 
	     for(int i=0,j=0;j<s.length();j++) {
	    	 while(index[s.charAt(j)]!=-1&&i<=j) {
	    		 index[s.charAt(i)]=-1;
	    		 i++;
	    	 }
	    	 index[s.charAt(j)]=j;//当前的j不在窗口内，我需要赋值，
	    	 //在窗口内部，我需要先删掉再赋值，所以这步操作少不了
	    	 result=Math.max(result, j-i+1);
	     }
	     return result;
	    }