要求

找出字符串中，最長(zhǎng)的沒有重復(fù)元素的子串，返回它的長(zhǎng)度。

示例

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.

求是求非手法

求是，就是判斷是不是符合條件的，這種做法可以過(guò)濾掉不符合條件的，它是針鋒相對(duì)的篩選，直接的思維，免去為數(shù)眾多的邊界條件和終止條件的判斷，是以快刀斬亂麻的方式取得結(jié)果的手段。
求非，是求是的反面，如果你覺得一個(gè)東西是什么你拿捏不準(zhǔn)，但是它不是什么你卻非常清楚，就可以通過(guò)判斷它不是什么來(lái)得到自己想要的結(jié)果。

劃窗

這是個(gè)技巧。想象一下數(shù)組像一把尺子，上面套了一個(gè)游標(biāo)，游標(biāo)長(zhǎng)短可調(diào)，除了游標(biāo)內(nèi)部的部分，尺子上其余的部分都不可見。這是一個(gè)解決字符串問(wèn)題的思維模型，每次處理劃窗內(nèi)的部分，這一招對(duì)于處理字符串的子串尤其有效，可以使時(shí)間復(fù)雜度降為O(n)。

代碼實(shí)現(xiàn)及用法

package com.company;

public class Main {

    public static void main(String[] args) {
    // write your code here
        String sourceString0 = "abcabcbb";
        String sourceString1 = "bbbbb";
        String sourceString2 = "pwwkew";
        String sourceString3 = "c";
        String sourceString4 = "aab";
        String sourceString5 = "dvdf";
        System.out.println(Solution.findLongestDistinctiveSubstring0(sourceString5));
    }
}

package com.company;

import java.util.*;

public class Solution {
    /**
     * 從前往后遍歷，以每遍歷到的元素為開始點(diǎn)
     * 再順序遍歷它后面的元素，只要沒碰到重復(fù)的就繼續(xù)。
     * 不斷重復(fù)此過(guò)程，直到源數(shù)組被遍歷完。
     * 它維持了一個(gè)哈希表，有沒有重復(fù)是通過(guò)判斷哈希表
     * 中的標(biāo)志位來(lái)判斷的。
     * 雖然這種算法能得到正確的結(jié)果，但是耗費(fèi)時(shí)間太長(zhǎng)。
     * 這種算法核心的思想還是雙重遍歷。
     * 但是經(jīng)過(guò)測(cè)試這個(gè)算法超時(shí)了，我需要改進(jìn)它。
     * @param sourceString
     * @return
     */
    static public int findLongestDistinctiveSubstring(String sourceString) {
        Map<Character,Boolean> flagMap = new HashMap<>();
        int maxSubstringLength = 0;
        for (int counter = 0;counter < sourceString.length();counter++) {
            for (int counter1 = 0;counter1 < sourceString.length();counter1++)
                flagMap.put(sourceString.charAt(counter1),false);
            for (int counter0 = counter;counter0 < sourceString.length();counter0++) {
                if (!flagMap.get(sourceString.charAt(counter0))) {
                    flagMap.put(sourceString.charAt(counter0),true);
                    if (counter0 - counter + 1 > maxSubstringLength)
                        maxSubstringLength = counter0 - counter + 1;
                } else break;
            }
        }
        return maxSubstringLength;
    }

    /**
     * 這是對(duì)方法的改進(jìn)以期把它的時(shí)間復(fù)雜度降到O(n)
     * 我的代碼實(shí)現(xiàn)并沒有很好地體現(xiàn)出我的想法，后來(lái)
     * 查了查資料原來(lái)這種想法名叫"劃窗"思想。就好像
     * 尺上的游標(biāo)，只不過(guò)這個(gè)游標(biāo)是可以調(diào)節(jié)長(zhǎng)短的。
     * 安裝這個(gè)劃窗以后，數(shù)組上面就是一片黑，除了這
     * 個(gè)劃窗里面。
     * 所謂花窗思想是指用兩個(gè)指針為邊界對(duì)之間內(nèi)容做
     * 邏輯處理的編程手法，這一招對(duì)于字符串的處理特別有效。
     * 更形象一點(diǎn)的話，整個(gè)過(guò)程有點(diǎn)像個(gè)毛毛蟲在那蠕動(dòng)一樣。
     * 有的時(shí)候從這個(gè)形象上面也能聯(lián)想到一些解決辦法。
     * 再有就是哈希表，這個(gè)哈希表我還是不想用數(shù)組來(lái)
     * 實(shí)現(xiàn)，我直接用hashset。
     * 另外，要想讓時(shí)間復(fù)雜度降下來(lái)就不能單獨(dú)處理hash
     * 表中的值，必須在每次遍歷的時(shí)候處理。
     * @param sourceString
     * @return
     */
    static public int findLongestDistinctiveSubstring0(String sourceString) {
        Set<Character> flagSet = new HashSet<>();
        int maxSubstringLength = 0;
        int startIndex = 0;
        int endIndex = 0;
        while (startIndex <= endIndex && endIndex < sourceString.length()) {
            if (!flagSet.contains(sourceString.charAt(endIndex))) {
                flagSet.add(sourceString.charAt(endIndex));
                if (endIndex - startIndex + 1 > maxSubstringLength)maxSubstringLength = endIndex - startIndex + 1;
                endIndex++;
            }
            else {
                //此時(shí)已經(jīng)找到了和startindex一樣的元素了，
                // endIndex指向了和startindex值相同的地
                // 方，換句話說(shuō)找到了重復(fù)的元素。并且此間所
                // 有的元素都不是重復(fù)的。
                flagSet.remove(sourceString.charAt(startIndex));
                startIndex++;
            }
        }
        System.out.println("最長(zhǎng)不重復(fù)子串為:" + sourceString.substring(startIndex,endIndex));
        return maxSubstringLength;
    }
}

輸出

最長(zhǎng)不重復(fù)子串為:vdf
3