【LeetCode】3、Longest Substring Without Repeating Characters（最长子串）

【LeetCode】3、Longest Substring Without Repeating Characters（最长子串）

1、题目描述

Given a string s, find the length of the longest substring without repeating characters.

找给定字符串中，最长的无重复字符的子串

做题过程：

当时题目理解错了，瞎鸡儿敲了敲，卒。

看答案！！！

2、暴力解法

其实最开始我敲的过程中有点像暴力解法，暴力解法就是莽。

两次循环把串中的所有子串都遍历出来，然后找子串中有没有重复元素。

最后取一个最长的子串输出。

以下是本人写的代码：

class Solution { public int lengthOfLongestSubstring(String s) { String inirt = s; if(s.length()==0){ return 0; } String test = ""; int length = 1; int max =0; for(int i =0;i<s.length();i++){ for(int j =i+1;j<s.length();j++){ boolean mar = find(i,j,inirt); if(mar){ if(j-i+1>=length){ length = j-i+1; } } } } return length; } public static boolean find(int i ,int j,String inrt){ String sub = inrt.substring(i,j+1); for(int m = 0;m<sub.length();m++){ char c = sub.charAt(m); int first = sub.indexOf(c); int last = sub.lastIndexOf(c); if(first!=last){ return false; } } return true; } }

可惜最后一个测试没过，超时了。。。

时间复杂度O(N3)

3、滑块解法

滑块解法顾名思义，就是将字符串想成一个滑块。

首先初始化滑块的左端l和右端r都是0，初始化字符set为空。检查串中r位置元素是否在字符set中,如不在，则将r元素插入set中，右端r向右移一位。更新最大子串的值。若在，则左端向右移一位（改进算法，左端直接移动到set中重复元素的位置即可）

例子（例子中的滑块是改进算法，直接滑到set中重复元素的位置）：

代码：

public class Solution { public int lengthOfLongestSubstring(String s) { int i=0,j=0,ans = 0; Set jf = new HashSet<>(); int n = s.length(); while(j<n&&i<n){ if(!jf.contains(s.charAt(j))){ jf.add(s.charAt(j++)); ans = Math.max(ans,j-i); } else{ jf.remove(s.charAt(i++)); } } return ans; } }

过了！时间复杂度O(n)

题解中还给出了改进算法的代码，使用hashmap实现

public class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(), ans = 0; Map<Character, Integer> map = new HashMap<>(); // current index of character // try to extend the range [i, j] for (int j = 0, i = 0; j < n; j++) { if (map.containsKey(s.charAt(j))) { i = Math.max(map.get(s.charAt(j)), i); } ans = Math.max(ans, j - i + 1); map.put(s.charAt(j), j + 1); } return ans; } } ans = Math.max(ans, j - i + 1); map.put(s.charAt(j), j + 1); } return ans; }

}