首页 > 其他 > 详细

LeetCode_03 无重复最长子串

时间:2020-02-17 23:53:22      阅读:111      评论:0      收藏:0      [点我收藏+]

题目描述

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

示例

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是?"wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke"?是一个子序列,不是子串。

知识点

  • 字符串+子串
  • 集合
  • 滑动窗口

滑动窗口

滑动窗口是数组/字符串问题中常用的抽象概念。
窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 [i, j)[i,j)(左闭,右开)。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。

可以把滑动窗口看成一个队列,向右滑动的时候,就是左边元素出队

解法

思路一 暴力破解

逐个检查所有的子字符串,看它是否不含有重复的字符。
需要枚举给定字符串的所有子字符串

 for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)

检查一个字符串是否有重复字符,我们可以使用集合。我们遍历字符串中的所有字符,并将它们逐个放入 set 中。在放置一个字符之前,我们检查该集合是否已经包含它。如果包含,我们会返回 false。循环结束后,我们返回 true。

//Java,leetcode官方题解
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }
}

思路二 滑动窗口

//未分析C++
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;
        unordered_set<char> lookup;//??
        int maxStr = 0;
        int left = 0;
        for(int i = 0; i < s.size(); i++){
            while (lookup.find(s[i]) != lookup.end()){
                lookup.erase(s[left]);
                left ++;
            }
            maxStr = max(maxStr,i-left+1);
            lookup.insert(s[i]);
    }
        return maxStr;
        
    }
};

todo list

  1. 知识点需要拓展
  2. 代码需要看懂
  3. 代码在VS上要跑通

LeetCode_03 无重复最长子串

原文:https://www.cnblogs.com/zhuomoyixia/p/12324321.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!