LeetCode

LeetCode-03 无重复字符的最长子串

nkul · 7月7日 · 2020年 249次已读
  • 目标:找到第i个元素结尾的无重复子串
  • 两个指针j和i:i用于遍历,j用于记录以第i个元素结尾的无重复子串的最左边
    • 当遍历到i+1时,以[i+1]为结尾的无重复子串,最左一定是在j之后
    • 用无序map记录(i,j)之间的元素
  • 遍历过程中,更新最长值,max(res,i-j+1)
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map < char,int > heap ;
        int res = 0;
        for(int i = 0,j = 0;i < s.size();i++){
            heap[s[i]]++;
            while(heap[s[i]] > 1) heap[s[j++]]--;
            res = max(res,i-j+1);
        }
        return res;
    }
};



0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!