原题：
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with the length of 1. Given "pwwkew", 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) {
}
}
大致意思，找到一个字符串的最大子串的长度，也就是无重复字符的最大长度
可以先将字符串用字符数据存起来，用两个下标，两层循环，都++，当a[i] == a[j]，记录长度，i从j+1开始，重复前一步
class Solution {
public int lengthOfLongestSubstring(String s) {
char[] charArray = s.toCharArray();
int len = charArray.length;
int longest = 0;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (charArray[i] == charArray[j]) {
if (longest < j - i) {
longest = j - i;
}
i = j;
}
}
}
return longest;
}
}
提交直接失败
Submission Detail 41 / 983 test cases passed. Status: Wrong Answer Submitted: 0 minutes ago Input: "c" Output: 0 Expected: 1
用例才执行了41个，看来还有很多情形没考虑进去，先仔细捋一捋，循环里只判断了有存在两个字符一样的情况，而整个字符串最大子串是自己本身这种情况没有考虑进去
定义一个flag，如果有相同的置为1
class Solution {
public int lengthOfLongestSubstring(String s) {
char[] charArray = s.toCharArray();
int len = charArray.length;
int longest = 0;
int flag = 0;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (charArray[i] == charArray[j]) {
flag = 1;
if (longest < j - i) {
longest = j - i;
}
i = j;
}
}
}
if (flag == 0) {
longest = len;
}
return longest;
}
}
提交一把，还是错误
Submission Detail 83 / 983 test cases passed. Status: Wrong Answer Submitted: 0 minutes ago Input: "aab" Output: 1 Expected: 2
仔细想了想，这实现方法就是搞笑的，找到两个相同的字符后，i = j毫无道理，按理说应该i从头到尾遍历，而j再在0-i之间来找最大子串
// a b c a b e
// 0 1 2 3 4 5
// i
// j
// i
// j j
// i
// j j j
// i
// j j j
比如：
i=1，j=0，最大子串长度longest=i-j+1=2
i=2，j=1，最大子串长度longest=i-j+1=2；j=0，最大子串长度longest=i-j+1=3>2；因此综合来看，此时最大子串长度为3
i=3，j=2，最大子串长度longest=i-j+1=2<3；j=1，最大子串长度longest=i-j+1=3=3；j=0，此时s[j]=s[i]，就没必要计算最大子串了（一定就是j=1的长度），但是更关键的一点，在下一轮循环i++的时候，j没必要遍历到j=0了，因为s[0]=s[3]，因此在有重复字符出现的时候，不计算最大子串长度，而是将j遍历的最小值变为相同字符时j的index值，这里就是1，下一轮循环开始j从i-1遍历到1即可
i=4，j=3，最大子串长度longest=i-j+1=2<3；j=2，最大子串长度longest=i-j+1=3=3；j=1，此时s[i]=s[j]，break，然后j的最小值变为1+1=2，下一轮循环j从i-1遍历到2
i=5，j=4，最大子串长度longest=i-j+1=2<3；j=3，最大子串长度longest=i-j+1=3=3；j=2，最大子串长度longest=i-j+1=4>3；此时结束，因此最大长度是4，子串也就是s[2]到s[5]，显然是正确的
综合以上，完成功能，其中空字符和只有一个字符不能忘了
class Solution {
public int lengthOfLongestSubstring(String s) {
int index = 0, longest = 0;
int len = s.length();
char[] ss = s.toCharArray();
if (len == 0) {
return 0;
}
if (len == 1) {
return 1;
}
// a b c a b e
// 0 1 2 3 4 5
// i
// j
// i
// j j
// i
// j j j
// i
// j j j
for (int i = 1; i < len; i++)
{
for(int j = i - 1; j >= index; j--)
{
if(ss[i] == ss[j])
{
index = j + 1;
break;
}
else
{
if(longest < i - j + 1)
longest = i - j +1;
}
}
}
return longest;
}
}
提交一把，可惜还是有问题
Submission Detail 979 / 983 test cases passed. Status: Wrong Answer Submitted: 0 minutes ago Input: "bbbbb" Output: 0 Expected: 1
如果字符串里是同一个字符，就全部break了，那么longest就返回初始值0了，不合要求，那就加一个判断，如果是这种情况就返回1，我这里用字符数组该字符长度来判断
class Solution {
public int lengthOfLongestSubstring(String s) {
int index = 0, longest = 0;
int len = s.length();
char[] ss = s.toCharArray();
int sameNum = 0;
if (len == 0) {
return 0;
}
if (len == 1) {
return 1;
}
for (char a : ss) {
if (a == ss[0]) {
sameNum ++;
}
}
if (sameNum == len) {
return 1;
}
// a b c a b e
// 0 1 2 3 4 5
// i
// j
// i
// j j
// i
// j j j
// i
// j j j
for (int i = 1; i < len; i++)
{
for(int j = i - 1; j >= index; j--)
{
if(ss[i] == ss[j])
{
index = j + 1;
break;
}
else
{
if(longest < i - j + 1) {
longest = i - j + 1;
}
}
}
}
return longest;
}
}
再提交，就可以了
Submission Detail 983 / 983 test cases passed. Status: Accepted Runtime: 51 ms Submitted: 0 minutes ago
4月2日改进版
package com.maoxiaomeng;
/**
* @author lihui
* @date 2018/3/26 12:31
*/
class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
if (len == 0) {
return 0;
}
int flag = 0;
for (int i = 0; i < len; i++) {
if (s.charAt(i) != s.charAt(0)) {
flag = 1;
break;
}
}
if (flag == 0 || len == 1) {
return 1;
}
int maxLen = 0;
int first = 0;
for (int i = 1; i < len; i++) {
for (int j = i - 1; j >= first; j--) {
if (s.charAt(i) == s.charAt(j)) {
first = j + 1;
break;
}
maxLen = Math.max(maxLen, i - j + 1);
}
}
return maxLen;
}
}
Leetcode上解决方法有人用hashset方式实现，比较顺眼
class Solution {
public int lengthOfLongestSubstring(String s) {
//a b c b e
int maxLength = 0;
int len = s.length();
int left = 0, right = 0;
HashSet<Character> hashSet = new HashSet<>();
while(left < len && right < len){
if (hashSet.contains(s.charAt(right))){
hashSet.remove(s.charAt(left++));
} else {
hashSet.add(s.charAt(right++));
maxLength = Math.max(maxLength, right - left);
}
}
return maxLength;
}
}
进一步优化下，就像上面index左边滑动一样
class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLength = 0;
int length = s.length();
int i = 0, j = 0;
HashMap<Character, Integer> hashMap = new HashMap<>();
for (; j < length; ++j){
if (hashMap.containsKey(s.charAt(j))){
i = Math.max(hashMap.get(s.charAt(j)) + 1, i);
}
maxLength = Math.max(maxLength, j - i + 1);
hashMap.put(s.charAt(j), j);
}
return maxLength;
}
}
