[Leetcode刷题] - LC003 Longest Substring without repating character
题目链接
Leetcode 003Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
https://leetcode.com/problems/longest-substring-without-repeating-characters/
题目描述
给定一个字符串，找到最长没有重复字符的子序列substring。
注：这里需要理解substring 和 subsequence 的区别，substring是指连续子串；而subsequence可以是非连续
题目思路
1. Brute Force
通常对于字符串求解符合某些条件的substring, 最简单的思路就是暴力搜索，两层循环即可
代码如下：
/** Brute force O(N^2) */if (s.length()==0) return 0;Set visited = null;int max = 1;for(int i=0; i();visited.add(s.charAt(i));int tMax = 1;for (int j=i+1; j 时间复杂度：；空间复杂度：
。
2. 同向双指针 - 滑动窗口
第一种思路也是一种同向双指针，每一次固定起始点指针，然后通过移动终止点指针来进行寻找不重复的子串。你会发现这种两重循环会引来很多不必要可以跳过的搜索。
如下例子，你会发现第二次循环时，从index=1 到 index=3这段是可以跳过的，因为我们知道 index - [0, 3]已经是一段不重复子串，[0,3]之间是不会再有更长的不重复子串的可能。所以我们完全可以跳过这段查找。
abcabb
^ ^ --- 第一次循环
^ ^ --- 第二次循环
第一次起始针在a [index=0的位置] , 然后遍历到 后面a [index=3]的位置结束
第二次起始点在 b [index=1的位置]，然后遍历到 后面 b [index=4]的位置结束
利用这个思路就可以优化这个滑动窗口，思路如下
1. 将起始点st固定在开头，然后开始移动终止点ed，移动ed期间记录字符是否使用过
2. 如果字符没有使用过，那么继续移动ed
3. 当发现ed移动到的字符出现重复，那么开始需要移动起始点st，怎么移动st？有两种情况
a. 重复字符位置在 [st, ed]窗口外边，这时说明窗口内还是不重复，继续移动ed即可
b. 如果重复字符在窗口内部，那么需要将起始点st移动到重复字符位置+1
4. 整个过程中不断更新不重复子串的长度即可
代码如下：
class Solution {public int lengthOfLongestSubstring(String s) {int[] chr = new int[128];Arrays.fill(chr, -1);if (s.length()==0) return 0;int st = 0;chr[s.charAt(st)-' '] = 0;int max = 0;int ed = 1;for (; ed时间复杂度：；空间复杂度：
，通过数组来保存ASCII码字符串大大降低空间复杂度。
上一篇：基于最小误差阈值法的特定医学图像分割算法研究-含Matlab代码
下一篇：web前端期末大作业——基于html+css+javascript+jquery+bootstrap响应式户外旅游网站