3.無重複字元的最長字元串.java 中等

問題描述

給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。

示例 1:

輸入: "abcabcbb"
輸出: 3 
解釋: 因為無重複字元的最長子串是 "abc"，是以其長度為 3。

示例 2:

輸入: "bbbbb"
輸出: 1
解釋: 因為無重複字元的最長子串是 "b"，是以其長度為 1。

示例 3:

輸入: "pwwkew"
輸出: 3
解釋: 因為無重複字元的最長子串是 "wke"，是以其長度為 3。
     請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。

來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
           

解法一：暴力

枚舉是以子字元串

利用Set判斷子字元串是否重複

Set繼承于Collection接口，是一個不允許出現重複元素，并且無序的集合，主要有HashSet和TreeSet兩大實作類。

在判斷重複元素的時候，Set集合會調用hashCode()和equal()方法來實作。

HashSet是哈希表結構，主要利用HashMap的key來存儲元素，計算插入元素的hashCode來擷取元素在集合中的位置；

TreeSet是紅黑樹結構，每一個元素都是樹中的一個節點，插入的元素都會進行排序；

參見詳解
https://www.jianshu.com/p/d6cff3517688
           

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans =0;
        for (int i = 0; i < n; i++){
            for (int j = i + 1; i < n; i++){
                if (allUnique(s,i,j)){
                    ans = Math.max(ans,j-i);
                }
            }
        }
        return ans;
    }
    public boolean allUnique(String s,int start,int end){
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++){
            Character ch = s.charAt(i);
            if (set.contains(ch)){
                return false;
            }
            set.add(ch);
        }
        return true;
    }
}
           

2.解法二

利用滑動視窗

class Solution {
    public 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){
            if(!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans,j-i);
            }
            else{
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}
           

3.解法三

滑動視窗優化

建立map，鍵值為元素，值為位置+1（友善i跳到相同元素的下一個位置）

若map中有相同元素，則i直接跳到這個元素的下一個位置，

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character,Integer> map = new HashMap<>();
        for (int i=0,j=0;j<n;j++){
            if(map.containsKey(s.charAt(j))){
                i = Math.max(map.get(s.charAt(j)),i);
            }
            map.put(s.charAt(j),j+1);
            ans = Math.max(ans,j-i+1);
        }
        return ans;
    }
}