Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Longest Substring Without Repeating Characters

Leetcode algorithms 第 3 题:Longest Substring Without Repeating Characters。

题目

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

解答

可以直接枚举每个起点,然后求最长长度,复杂度O(n^2)。或者直接遍历整个数组,记录每个数字最近一次出现的位置,

  • 如果最近一次出现的位置比当时的起点还要早,则该数字在当前的子串中仍属于第一次出现,仍可以继续往后走,只需更新这个位置即可。
  • 如果最近一次出现的位置比当时的起点还要玩,则该数字已经出现两次了,需要更新起点,显然,这个起点至少要在该数字第一次出现的位置之后,再更新其他统计量即可。

使用哈希表记录每个数字当前最近出现的位置,则复杂度为O(n)。

代码如下:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0, cur = 0; //最终答案,此次答案
        unordered_map<char, int> mp;
        for (int i = 0, st = 0; i < s.size(); i++) //st为此次起点
        {
            if(m.find(s[i]) == m.end()) //s[i]在st后第一次出现
                cur++, m[s[i]] = i;
            else                        //已经出现过
            {
                if (m[s[i]] < st)       //出现的位置在st前,起点不变
                    cur++, m[s[i]] = i;
                else                    //出现的位置在st后,更新起点
                    st = m[s[i]] + 1, cur = i - st + 1, m[s[i]] = i;
            }
            ans = max(ans, cur); //更新最长长度
        }
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论