LeetCode-LongestSubstringWithoutRepeatingCharacters

2019-11-14 14:52:30

字體：大中小

來源：轉載

供稿：網友

題目：

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

思路：

1) 兩個for循環，用map存訪問過的字母，遇到相同的就停止，然后再從這個相同字母的下一個字母開始。超時了。

package string;import java.util.HashMap;public class LongestSubstringWithoutRepeatingCharacters {    public int lengthOfLongestSubstring(String s) {        int len;        if (s == null || (len = s.length()) == 0) return 0;        HashMap<Character, Integer> map = new HashMap<Character, Integer>();        int max = 0;        for (int i = 0; i < len; ++i) {            map.put(s.charAt(i), i);            for (int j = i + 1; j < len; ++j) {                if (!map.containsKey(s.charAt(j))) {                    map.put(s.charAt(j), j);                } else {                    i = map.get(s.charAt(j));                    break;                }            }                        int count = map.size();            if (count > max) {                max = count;            }            map.clear();        }                return max;    }        public static void main(String[] args) {        // TODO Auto-generated method stub        String s = "abcabcbb";        LongestSubstringWithoutRepeatingCharacters l = new LongestSubstringWithoutRepeatingCharacters();        System.out.PRintln(l.lengthOfLongestSubstring(s));    }}

2）對方法一的簡化，保持重復元素的上一個位置，往前挪動，不斷計算

package string;import java.util.HashMap;public class LongestSubstringWithoutRepeatingCharacters {    public int lengthOfLongestSubstring(String s) {        int len;        if (s == null || (len = s.length()) == 0) return 0;        HashMap<Character, Integer> map = new HashMap<Character, Integer>();        int max = 0;        int lastIndex = -1;        for (int i = 0; i < len; ++i) {            char c = s.charAt(i);            if (map.containsKey(c) && lastIndex < map.get(c)) {                lastIndex = map.get(c);            }                        if (i - lastIndex > max)                max = i - lastIndex;            map.put(c, i);        }                return max;    }        public static void main(String[] args) {        // TODO Auto-generated method stub        String s = "abcabcbb";        LongestSubstringWithoutRepeatingCharacters l = new LongestSubstringWithoutRepeatingCharacters();        System.out.println(l.lengthOfLongestSubstring(s));    }}