给定一个字符串，找到没有重复字符的最长子串的长度。
例如:
字符串”abcabcbb”, 最长非重复子串长度是3(“abc”).
字符串”pwwkew”, 最长非重复子串长度是3(“wke”).
暴力求解
简单粗暴的方法就是找到以字母i开头的非重复子串，比较其长度，找到最大的值。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> hashmap = new HashMap<Character, Integer>();
char[] charArr = s.toCharArray();
int lengthest = 0;
for (int i=0; i<charArr.length; i++){
hashmap.put(charArr[i],1);
int length = 1;
for (int j=i+1; j<charArr.length; j++){
if (hashmap.containsKey(charArr[j])){
break;
}
hashmap.put(charArr[j], 1);
length++;
}
if (length > lengthest){
lengthest = length;
}
hashmap.clear();
}
return lengthest;
}
}
|
以i为前缀，然后遍历i+1，用HashMap存放遍历过的字符。
指针
通过两个指针start和end来标识一个非重复的子串sub，然后遍历字符串中的每个字符，判断是否在sub中有重复，没有则通过移动end指针，将当前字符加入sub中，有重复的则通过移动start指针对sub的起始位置进行重新标识(可以一个字符一个字符的移动，也可以直接移动到sub中发生重复字符的下一个位置)。代码如下：
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
31
32
33
| public class Solution {
public int lengthOfLongestSubstring(String s) {
int lengthest = 0;
char[] charArr = s.toCharArray();
int start = 0;
int end = 0;
int length = 0;
for (int i=1; i<charArr.length; i++){
end = i - 1;
for (int j=start; j<i; j++){
if (charArr[i] == charArr[j]){
length = end - start + 1;
if (length > lengthest){
lengthest = length;
}
start = j + 1;
length = 0;
}
}
}
length = charArr.length-1 - start + 1;
if (length > lengthest){
lengthest = length;
}
return lengthest;
}
}
|
时间复杂度是n的平方，但是空间复杂度是0，则是否可以通过增加空间复杂度来减少时间复杂度。从代码中可以看到，第二个for循环主要就是从当前子串中查找是否有重复的字符并找到该字符的索引，这明显是一个key/value的结构，则可以使用map，通过O(1)的时间复杂度来找到重复的字符对应的索引。
这种平滑指针的方法也叫平滑窗口，平滑窗口是一个抽象的概念，通常用于解决数组和字符串的问题。
下面看下优化后的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public class Solution {
public int lengthOfLongestSubstring(String s) {
int lengthest = 0;
Map<Character, Integer> map = new HashMap<Character, Integer>();
char[] chars = src.toCharArray();
for (int start=0,end=0; end<chars.length; end++){
if (map.containsKey(chars[end])){
start = Math.max(map.get(chars[end]), start);
}
lengthest = Math.max(lengthest, end - start + 1);
map.put(chars[end], end + 1);
}
return lengthest;
}
}
|
动态规划
还有一种思路是动态规划，这也是最优的一种。
动态规划往往用于求解最优解(最大值、最短路径、最长公共子序列)问题。
动态规划简介
动态规划的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题(阶段)。按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解()最优解。依次解决各子问题，最后一个子问题就是初始问题的解。
动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推(或者说分治)的方式去解决。则动态规划的本质是状态的定义和状态转移方程
动态规划通过拆分问题，将原始问题拆分为子问题，而各子问题之间的关系是后一子问题的解往往又前一子问题的解求出，则**子问题之间是重叠的(则不是相互独立的)**，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
动态规划与分治法最大的差别是:适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。
适用条件
能采用动态规划求解的问题的一般要具有3个性质：
(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
(3) 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
下面来看下用动态规矩解决此问题的代码：
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
| public class Solution {
public int lengthOfLongestSubstring(String s) {
int lengthest = 0;
char[] chars = src.toCharArray();
int[] dp_status = new int[chars.length];
Map<Character, Integer> hashMap = new HashMap<Character, Integer>();
int start = 0;
for (int i=0; i<chars.length; i++){
if (hashMap.containsKey(chars[i])){
start = Math.max(start, hashMap.get(chars[i]));
dp_status[i] = i - start + 1;
hashMap.put(chars[i], i+1);
continue;
}
hashMap.put(chars[i], i+1);
if (i == 0){
dp_status[i] = 1;
continue;
}
dp_status[i] = dp_status[i-1] + 1;
}
for (int length : dp_status){
if (length > lengthest){
lengthest = length;
}
}
return lengthest;
}
}
|
通过在leetcode上提交代码发现，使用HashMap来查询重复字符的方法貌似没有直接用for循环逐个字符匹配执行的快。
附加：递归与递推
递归是一个程序调用自身
递推就是迭代
wechat