LeetCode面试算法-力扣 3. 无重复字符的最长子串

3. 无重复字符的最长子串

题目描述

    给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

---

示例 1:
    输入: "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
    输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
    输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

---

分析：滑动窗口，int[] m = new int[256]创建256大小的整型数组储存256个ASCII字符，res表示最长无重复子串的长度，left表示无重复子串左窗口下标，遍历字符串并移动左窗口，i - left １计算最长无重复子串，ｉ表示最长无重复子串最右边的位置，left表示最左边的位置，以字符串"abcabcbb"为例：

        i=0   s.charAt(i)=a   m[s.charAt(i)]=0   left=0   res=1
        i=1   s.charAt(i)=b   m[s.charAt(i)]=0   left=0   res=2
        i=2   s.charAt(i)=c   m[s.charAt(i)]=0   left=0   res=3
        i=3   s.charAt(i)=a   m[s.charAt(i)]=1   left=1   res=3
        i=4   s.charAt(i)=b   m[s.charAt(i)]=2   left=2   res=3
        i=5   s.charAt(i)=c   m[s.charAt(i)]=3   left=3   res=3
        i=6   s.charAt(i)=b   m[s.charAt(i)]=5   left=5   res=3
        i=7   s.charAt(i)=b   m[s.charAt(i)]=7   left=7   res=3

---

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] m = new int[256];
        int res = 0, left = 0;
        for (int i = 0; i < s.length(); i  ) {
            left = Math.max(left, m[s.charAt(i)]);
            res = Math.max(res, i - left   1);
            m[s.charAt(i)] = i   1;
        }
        return res;
    }
}

 

到此这篇关于“LeetCode面试算法-力扣 3. 无重复字符的最长子串”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！

您可能感兴趣的文章：
LeetCode面试算法-力扣 3. 无重复字符的最长子串
leetcode算法题—golang—无重复的字符的最长子串（题3）
53. 最大子序和 golang （动态规划与贪心算法）
php字符串函数有哪些
python如何使用正则表达式
mysql 某个字段替换某个名词
php全局变量之学习笔记
php计算未知长度的字符串中出现的次数最多字符的代码
python string是什么
腾讯php程序员面试题分享