leetcode-3-無重複字元的最長子串

題目：

暴力解法：枚舉出所有的子字元串，再根據子字元串來判斷，使用枚舉用了三層循環，時間複雜度為O(N2)

package com.example.demo;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class TestLeetCode {
    /**
     * 查找給定字元串中長度最長的子字元串的長度（本題不需要給出具體的字元串）
     *
     * @param args
     */
    public static void main(String[] args) {
        int abcabcbb = lengthOfLongestSubstring("abcabcbb");
        System.out.println(abcabcbb);
    }

    /**
     * 暴力解法，枚舉出所有的子字元串，并且子字元串無重複字元，找到長度最長的子字元串
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        int maxRes = 0;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j <= len; j++) {
                System.out.println(s.substring(i, j));
　　　　　　　　　//如果子字元串沒有重複字元，則重新計算maxRes　　
                if (allUnique(s, i, j)) {
                    maxRes = Math.max(maxRes, j - i);
                }
            }
        }
        return maxRes;
    }

    /**
     * 判斷i-j之間的字元串是否是沒有重複的字元
     */
    private static boolean allUnique(String s, int start, int end) {
        Set<Character> contains = new HashSet<>();
        for (int i = start; i < end; i++) {
            char c = s.charAt(i);
            if (contains.contains(c)) {
                return false;
            }
            contains.add(c);
        }
        return true;
    }

    /**
     * 枚舉出的所有子字元串
     * a
     * ab
     * abc
     * abca
     * abcab
     * abcabc
     * abcabcb
     * abcabcbb
     * b
     * bc
     * bca
     * bcab
     * bcabc
     * bcabcb
     * bcabcbb
     * c
     * ca
     * cab
     * cabc
     * cabcb
     * cabcbb
     * a
     * ab
     * abc
     * abcb
     * abcbb
     * b
     * bc
     * bcb
     * bcbb
     * c
     * cb
     * cbb
     * b
     * bb
     * b
     */
}      

滑動視窗法：

package com.example.demo;

import java.util.HashSet;
import java.util.Set;

public class TestLeetCode {
    /**
     * 查找給定字元串中長度最長的子字元串的長度（本題不需要給出具體的字元串）
     *
     * @param args
     */
    public static void main(String[] args) {
        int abcabcbb = lengthOfLongestSubstring("abcabcbb");
        System.out.println(abcabcbb);
    }

    /**
     * 滑動視窗法，通常情況下在數組和字元串中經常用到
     * 該方式會定義兩個索引，left = 0; right = 0; 開始時，left = right,此時left到right之間沒有重複的字元，
     * 此時right++，然後在判斷left到right之間是否有重複字元，沒有則right++，重複該過程，
     * 如果存在重複字元是，則left++，
     * 然後繼續走之前的循環，知道right==length時結束
     */
    public static int lengthOfLongestSubstring(String s) {
        int maxRes = 0;
        int left = 0, right = 0;
        Set<Character> contains = new HashSet<>();
　　　　　//當left和right小于s.length是，繼續循環
        while (left < s.length() && right < s.length()) {
　　　　　　　//擷取right索引出的字元
            char c = s.charAt(right);
　　　　　　　//判斷right索引處的字元是否在left和right-1中出現過（這個借助的一個hashset結構來實作）
            if (contains.contains(c)) {
　　　　　　　　　　//出現過，則左索引自增，同僚移除hashset中的c
                left++;
                contains.remove(c);
            } else {
　　　　　　　　　　//沒有出現過，則将目前字元添加到hashset中，同僚right向後移位，并更新maxRes的值
                contains.add(c);
                right++;
                maxRes = Math.max(maxRes, right - left);
            }
        }

        return maxRes;
    }

}