本文共 2263 字，大约阅读时间需要 7 分钟。

题目

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"Output: 3 Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"Output: 1Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"Output: 3Explanation: 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.

我的尝试

分析：1. 最长的子串 2 不重复字符

开始条件：遍历字符串所有字符

终止条件：出现重复字符

返回：当前的字符串长度

没有思路，通过分析答案，发现可以利用“滑动窗口”思路解决“连续子串”的问题。思路如下：

设置两个指针i和j，初始化i和j都等于0.遍历数组，比较元素是否重复，如果不重复，则j指针顺序后移，如果发现重复的元素，i从下一个元素开始，j不变，循环直到数组结束

package com.puhui.goosecard.web;import java.util.HashMap;import java.util.Map;class Solution {    public static int lengthOfLongestSubstring(String s) {        int max = 0;        Map
   
     map = new HashMap();        for (int i = 0, j = 0; j < s.length(); j++) {            if (!map.containsKey(s.charAt(j))) {                //不存在，放入map，计算最大长度                max = Math.max(max, j - i + 1);                map.put(s.charAt(j), j);            } else {                //存在，移动i                i++;            }        }        return max;    }    public static void main(String[] args) {        String s = "abcabe";        System.out.println(lengthOfLongestSubstring(s));    }}
   

运行没有问题，但是leetcode测试没有通过，又是重复元素问题，我的代码没有考虑重复元素情况。

滑动窗口算法

package com.puhui.goosecard.web;import java.util.HashSet;import java.util.Set;class Solution {    public static int lengthOfLongestSubstring(String s) {        int n = s.length();        Set
   
     set = new HashSet<>();        int ans = 0, i = 0, j = 0;        while (i < n && j < n) {            // try to extend the range [i, j]            if (!set.contains(s.charAt(j))) {                set.add(s.charAt(j++));                ans = Math.max(ans, j - i);            } else {                set.remove(s.charAt(i++));            }        }        return ans;    }    public static void main(String[] args) {        String s = "pwwkew";        System.out.println(lengthOfLongestSubstring(s));    }}
   

• 集合set作为滑动窗口，记录当前满足条件的最长元素集合
• 初始化ij相等，都等于0。循环数组，如果j对应元素不存在set中，继续右移动，扩大窗口范围。记录当前size，并进行比较，记录最大size
• 如果j的元素一旦在set中存在，移除set中的第一个元素，也就是移动左侧指针i，缩小窗口范围。
• 直到i 和j其中一个大于数组长度终止循环

转载地址：https://kerry.blog.csdn.net/article/details/83151732 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！