本文為個人解題思路整理，水平有限，有問題歡迎交流

概覽

第一次解出來沒花多長時間，但是提交后發(fā)現(xiàn)擊敗了30%的人，也就是意味著還有大幅度優(yōu)化的空間，于是再優(yōu)化了一下

難度：中等

核心知識點：滑動窗口 + 貪心

題目來源

力扣：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

題目內(nèi)容

給定一個字符串，請你找出其中不含有重復(fù)字符的 最長子串 的長度

樣例

輸入1

pwwkew

輸出1

3

解釋1

最長無重復(fù)為wke

解題思路

明顯這是一個滑動窗口問題，即一個長度為L的窗口從左往右滑動，找到符合情況的最大L，下面進行思路分析

• 我們需要確定目標(biāo)的長度，那么需要知道頭head和尾tail，并確保中間的所有元素不重復(fù)

• 對于一個子串，如果存在重復(fù)元素，那么包含這個子串的任何其他子串也存在重復(fù)元素

• 貪心：即盡可能追求更多，若一個子串滿足要求，那么考慮這個子串與相鄰的字符能否組成更大的子串，進而將子串?dāng)U充，子串越大越好，因此得到的結(jié)果是對于每個起點，只有一個最遠的終點，即每個起點對應(yīng)最多一個結(jié)果

  比如子串p符合要求，那么考慮pw也符合要求，那么考慮pww不符合要求，則已p開頭的最長子串是pw，不可繼續(xù)貪心

• 滑動：前面說了pww的最長子串是pw，那么對于pww****呢？*代表暫時未知的字符，如果后面的結(jié)果比pw長呢？那么我們也需要搜索后面的字符串，但是兩個w不能重復(fù)，于是不得不放棄一個w，

  • 放棄后一個的結(jié)果就是pw
  • 放棄前一個的結(jié)果是solve("w****")，resolve表示解決方法

  也就是說 solve("pww****") = max(resolve("pw"), soleve("pw****"))

  在對soleve("pw****")同樣的方法處理下去，即可拿到最終的最大值

  比如對于目標(biāo)字符串abcadefa，處理步驟如下（偷個懶，resolve省掉啦，不然看上去很亂）

  //第一次處理,兩個a不同,必須放棄其中一個
  solve("abcdadfa")=max(solve("abcd"),solve("bcdadfa"));
  solve("abcd")=4;
  //第二次處理，兩個d不同
  solve("bcdadfa")=max(solve("bcda"),solve("adfa"));
  solve("bcda")=4;
  //第三次處理，兩個a不同
  solve("adfa")=max(solve("adf"),solve("dfa"));
  solve("adf")=3;
  solve("dfa")=3;
  //那么最終結(jié)果為4
  solve("abcdadfa")=max(4,max(4,max(3,3)))=max(4,4,3,3)=4
  

  即從左往右貪心出最長的不重復(fù)字符串，直到出現(xiàn)一個與已有字符重復(fù)的目標(biāo)，就貪不動了

  這時候考慮放棄已有字符的和放棄新字符兩種情況，取兩種情況的結(jié)果最大的那個

  • 放棄新字符，即當(dāng)前子串的長度就是結(jié)果，我們一直在保證沒有重復(fù)字符嘛
  • 放棄舊字符，則從舊字符的下一位開始下一步檢索，對新的目標(biāo)重復(fù)貪心和處理

解決方案

1. 設(shè)置兩個指針 left 和 right ，初識均指向字符串的頭部，設(shè)置初始最大長度ans = 0

2. 記錄right目標(biāo)的字符和位置，right 右移，直至其目標(biāo)字符已出現(xiàn)過，開始處理

   1. 放棄新字符，則舊字符串的長度為 right-left，修改ans = max(ans, right - left)
   2. 放棄舊字符，若舊字符位置的oldPosition，則 left 修改為oldPosition + 1

   即得到新的字符串

3. right 繼續(xù)右移，重復(fù)第二步

完整代碼

這里使用數(shù)組存儲位置，而非map，因為字符可按ASCII碼存儲，顯然一個int[128]是比map的效率更高

package com.company;

import java.util.*;

/**
 * @title 無重復(fù)字符的最長子串
 * @description 力扣3
 * @author Echo_Ye
 * @date 2020/9/22 11:56
 * @email echo_yezi@qq.com
 */
public class LengthOfLongestSubstring {
    public static void main(String[] args) {
        new LengthOfLongestSubstring();
    }

    public LengthOfLongestSubstring() {
        int ans = lengthOfLongestSubstring("abcdadfa");
        System.out.println(ans);
    }

    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        int left = 0, right = 0;
        int[] map = new int[128];
        Arrays.fill(map, -1);
        while (right <= s.length()) {
            if (right == s.length()) {
                //結(jié)算，結(jié)束查找
                ans = max(ans, right - left);
                break;
            }
            //檢查right目標(biāo)
            if (left == right || map[s.charAt(right)] == -1 || map[s.charAt(right)] < left) {
                //存儲位置
                map[s.charAt(right)] = right;
                //指針重疊的時候，右指針右移1
                //右指針目標(biāo)未出現(xiàn)過的時候，右指針右移1
                right++;
            } else {
                //結(jié)算，left移至舊字符右1位置
                ans = max(ans, right - left);
                left = map[s.charAt(right)] + 1;
            }
        }
        return ans;
    }

    int max(int a, int b) {
        return a > b ? a : b;
    }
}

結(jié)果

image-20200922115834734

性能

image-20200922115900594

后記

沒有涉及什么高深的算法，就是思路靈活轉(zhuǎn)換而已，好吧其實涉及到高級算法我可能就不會做了哈哈哈哈哈

作者：Echo_Ye

WX：Echo_YeZ

Email ：echo_yezi@qq.com

個人站點：在搭了在搭了。。。（右鍵 - 新建文件夾）