【題解】LeetCode 3. Longest Substring Without Repeating Characters

題目敘述:https://leetcode.com/problems/longest-substring-without-repeating-characters/
解題想法:Two Pointers【筆記

  • 【圖例】輸入字串”pwwkew”,求不含重複字元的最長子字串長度。
  • sq[128]:字元轉換成ASCII code,紀錄某字元最近一次出現的順位。(初始值為 -1,順位從 1 起算。)
  • 利用指標 r 往右掃描字串。
  • 更新指標 l 的方法:如果遇到出現過的字元,就把指標 l 移動到sq[s[r]]的位置,再計算子字串長度。
  • 記得更新 s[r] 出現的順位。
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.size();
        int sq[128] = {0};
        int mx = 0;
        for (int l=0, r=0; r<len; r++){
            l = max(sq[s[r]], l);
            mx = max(mx, r - l + 1);
            sq[s[r]] = r + 1;
        }
        return mx;
    }
};
分享本文 Share with friends