3. Longest Substring Without Repeating Characters
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.
首先看到这个题就要想到怎么来处理。
O(N^2)做法
以第一层for循环的i为子串的结尾遍历一遍母串
然后pos为每一个串的开头,只要有相同的那么下一个串,结尾是i+1,已经包括了i,i跟前面的有冲突,记录为j,所以pos记录为j+1,从没冲突的开始即可。
用Max记录每一个串的最大长度:
public class Solution { public int lengthOfLongestSubstring(String s) { if(s.length()==0) return 0; int pos = 0; int Max = 1; int flag = 0; int cnt = 1; String ans = ""; for(int i = 1; i < s.length(); i++) { flag = 0; for(int j = pos; j < i; j++) { if(s.charAt(i) == s.charAt(j)) { flag = 1; pos = j+1;//如果有相同的,那么下一个遍历的点就要跳过这个,集合不能包括这个 break; } cnt++; } Max = Max>cnt?Max:cnt; cnt = 1; } return Max; } }
O(n)做法,HashSet维护
就是利用了hashset来判断,降到了O(2n)。
话说HashSet这里的contain查找速度是默认认为是O(1)了吗,果然还是要啃下源码啊。
import java.util.*; public class leetcode3LongestSubstring { public static int lengthOfLongestSubstring(String s) { int n = s.length(); Set<Character> set = new HashSet<>(); int ans = 0, i = 0, j = 0; while (i < n && j < n) { // try to extend the range [i, j] if (!set.contains(s.charAt(j))){ set.add(s.charAt(j++));//j必须++,减去i才是区间长度 ans = Math.max(ans, j - i); } else { set.remove(s.charAt(i++)); } } return ans; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.next(); System.out.println(lengthOfLongestSubstring(s)); } }
比如 abcdbef,i和j指针开始都0位置a上,set添加a
添加b
添加c,d
到j位4,指向b,这时候要删除前段串,j停在b,a一直删到c,也就是set去掉了a,b,从出现的重复字符的下一个位置开始,当做当前子串的起始位置。
添加e
添加f
i,j任意一个到达n结束。
O(N)的另一种做法 HashMap
import java.util.*; public class leetcode3LongestSubstring { public static 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; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.next(); System.out.println(lengthOfLongestSubstring(s)); } }
把每个字符key对应的value为自己的下标+1,这个就是遇到重复字符时起始点i要跳越的位置。和上个算法思路一样。
所以我们也直接可以用一个数组来解决,话说我还是第一次知道int数组,下标也可以为字符类型,默认会转为对应的ASCII码,记住两个A:65,a:97,A和a除了26个字母还有6个其他字符。
public class Solution { 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++) { i = Math.max(index[s.charAt(j)], i); ans = Math.max(ans, j - i + 1); index[s.charAt(j)] = j + 1; } return ans; } }