接下來我會找出LeetCode中一些比較有代表性的題，帶來它的算法和講解

很多題目，使用一般的暴力算法很多都能解出來，但時間復雜度可能是 O(n3)，會比最優解慢很多，尤其是數據量變大時。

在我們實際項目中編寫代碼時會遇到各種情況，組織數據，處理數據，如果能在特定的情況使用特定的算法，就可以發揮事半功倍的效果，很有現實意義。

原題鏈接

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

示例 :
輸入: "abcabcbb" 輸出: 3 解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。

暴力

這是一個比較經典的問題，查找無重復最長子串。

先看我最開始給出的解法

思路比較簡單，借助Set，我可以很快的判斷一個字符是否在一個集合里

從第一個字符開始開始遍歷每個字符，然后從這個字符開始到最后一個字符，依次加入Set

如果Set沒有就加入，一旦出現重復判斷之前的最長長度和當前的最長長度，取較大值，Set清空

class Solution {public int lengthOfLongestSubstring(String s) {Set<Integer> t = new HashSet<>();int max = 0;for (int i = 0; i < s.length(); i++) {for (int j = i; j < s.length(); j++) {int a = s.charAt(j);if (!t.contains(a)) {t.add(a);} else {max = t.size() > max ? t.size() : max;t.clear();break;}}}if(t.size() > max){max = t.size();}return max;} }

滑動窗口

先看解法

class Solution {public int lengthOfLongestSubstring(String s) {int max = 0;Set<Character> t = new HashSet<>();for (int i = 0, j = 0; i < s.length(); ) {if (j >= s.length()) {break;}if (!t.contains(s.charAt(j))) {t.add(s.charAt(j));max = Math.max(max, j - i +1);j++;}else{t.remove(s.charAt(i++));}}return max;} }

暴力法有個明顯的問題，比如我判斷 abcabcbb

在第一字符時判斷

a ab abc abca

在第二個字符時判斷

b bc bca

會有大量重復且不必要的判斷

那么怎么避免呢

當我判斷第一個字符到 abca 時，不在完全退回第二個字符重新判斷，而是保留右側的配置，左側右移一位，那么現在就成了不重復時右側游標右移，存在重復字符時，左側游標右移，同時記錄中間的最長長度

左側游標和右側游標依次滑動右移，就仿佛是一個會移動的窗口，中間的某個最大長度即為不含有重復字符的最長子串

滑動窗口優化

當我們遇到一個字符串pasdsad，使用上述算法

p pa pas pasd asd sd d ds

因為下一個字符是s，所以左側游標移動了3次才移除了當前窗口內s

但是如果直接能跳到s位置呢

那么又會減少很多次操作

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

通過Map映射記錄上一個重復字符的位置，發生重復是可使左側游標直接跳到之前的重復位置。

關注我的Github項目，開啟Java進階之路，歡迎star

Asens/Java-Advance?github.com

總結

以上是生活随笔為你收集整理的cstring判断是否包含子串_最长子串-滑动窗口的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。