最长子字符串的算法题总结
题目
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
我的解法：
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0) {
return 0;
}
int maxCount = 0;
int count = 0;
char[] chars = s.toCharArray();
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < chars.length; i++) {
if (map.containsKey(chars[i])) {
//找到相同字符后，将找到的上一个值的索引值赋值给i，从i+1开始，重新计算子字符串
i = map.get(chars[i]);
map.clear();
maxCount = Math.max(maxCount, count);
count = 0;
} else {
count++;
map.put(chars[i], i);
}
}
maxCount = Math.max(maxCount, count);
return maxCount;
}
}
最优解法：
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128]; // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
//这里使用Math.max比较，如果在数组index中找到重复字符，则应为这个索引值，
//如果没找到，则应该为上一次找到重复字符的索引值
i = Math.max(index[s.charAt(j)],i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;
}
return ans;
}
总体印象：
1.最优解法的实现很优雅，但比较难懂；
2.特别是这里的Math.max方法很是难懂
写了几个简单的递归，递归的边界条件以及退出条件，在写之前需要好好考虑清楚。
最长子字符串的算法题总结 题目 Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2: Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3: Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring. 我的解法： class Solution { public int lengthOfLongestSubstring(String s) { if(s == null || s.length() == 0) { return 0; } int maxCount = 0; int count = 0; char[] chars = s.toCharArray(); Map<Character, Integer> map = new HashMap<>(); for (int i = 0; i < chars.length; i++) { if (map.containsKey(chars[i])) { //找到相同字符后，将找到的上一个值的索引值赋值给i，从i+1开始，重新计算子字符串 i = map.get(chars[i]); map.clear(); maxCount = Math.max(maxCount, count); count = 0; } else { count++; map.put(chars[i], i); } } maxCount = Math.max(maxCount, count); return maxCount; } } 最优解法： public int lengthOfLongestSubstring(String s) { int n = s.length(), ans = 0; int[] index = new int[128]; // current index of character // try to extend the range [i, j] for (int j = 0, i = 0; j < n; j++) { //这里使用Math.max比较，如果在数组index中找到重复字符，则应为这个索引值， //如果没找到，则应该为上一次找到重复字符的索引值 i = Math.max(index[s.charAt(j)],i); ans = Math.max(ans, j - i + 1); index[s.charAt(j)] = j + 1; } return ans; } 总体印象： 1.最优解法的实现很优雅，但比较难懂； 2.特别是这里的Math.max方法很是难懂