溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了leetcode中如何查看無重復字符的最長子串，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
給定一個字符串，請你找出其中不含有重復字符的 最長子串 的長度。
示例 1:
輸入: "abcabcbb"輸出: 3 解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。
示例 2:
輸入: "bbbbb"輸出: 1解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。
示例 3:
輸入: "pwwkew"輸出: 3解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3。 請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。
標簽：滑動窗口
暴力解法時間復雜度較高，會達到O(n^2)，故而采取滑動窗口的方法降低時間復雜度
定義一個map數據結構存儲(k,v)，其中key值為字符，value值為字符位置+1，加1表示從字符位置后一個才開始不重復
我們定義不重復子串的開始位置為start，結束位置為end
隨著end不斷遍歷向后，會遇到與[start, end]區間內字符相同的情況，此時將字符作為key值，獲取其value值，并更新start，此時[start, end]區間內不存在重復字符
無論是否更新start，都會更新其map數據結構和結果ans。
時間復雜度：O(n)
class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(), ans = 0; Map<Character, Integer> map = new HashMap<>(); for (int end = 0, start = 0; end < n; end++) { char alpha = s.charAt(end); if (map.containsKey(alpha)) { start = Math.max(map.get(alpha), start); } ans = Math.max(ans, end - start + 1); map.put(s.charAt(end), end + 1); } return ans; }}
感謝你能夠認真閱讀完這篇文章，希望小編分享的“leetcode中如何查看無重復字符的最長子串”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
