{"id":7381,"date":"2026-07-21T00:44:17","date_gmt":"2026-07-20T16:44:17","guid":{"rendered":"https:\/\/i007.cc\/wordpress\/?p=7381"},"modified":"2026-07-21T00:44:17","modified_gmt":"2026-07-20T16:44:17","slug":"%e6%9c%80%e9%95%bf%e4%b8%8d%e9%87%8d%e5%a4%8d%e5%ad%90%e4%b8%b2%ef%bc%88longest-substring-without-repeating-characters%ef%bc%89","status":"publish","type":"post","link":"https:\/\/i007.cc\/wordpress\/archives\/7381","title":{"rendered":"\u6700\u957f\u4e0d\u91cd\u590d\u5b50\u4e32\uff08Longest Substring Without Repeating Characters\uff09"},"content":{"rendered":"

\u529b\u6263\u7b2c 3 \u9898\u3002\u627e\u51fa\u4e00\u4e2a\u5b57\u7b26\u4e32\u4e2d\uff0c\u4e0d\u542b\u91cd\u590d\u5b57\u7b26\u7684\u6700\u957f\u5b50\u4e32<\/strong>\u7684\u957f\u5ea6\u3002<\/p>\n

\n

\u6838\u5fc3\u601d\u8def\uff1a\u6ed1\u52a8\u7a97\u53e3<\/h4>\n

\u7ef4\u62a4\u4e00\u4e2a\u7a97\u53e3 [left, right)<\/code>\uff0c\u4fdd\u8bc1\u7a97\u53e3\u5185\u6c38\u8fdc\u6ca1\u6709\u91cd\u590d\u5b57\u7b26\u3002right<\/code> \u4e0d\u65ad\u5411\u53f3\u6269\u5f20\uff0c\u4e00\u65e6\u9047\u5230\u91cd\u590d\u5b57\u7b26\uff0c\u5c31\u628a left<\/code> \u5411\u53f3\u6536\u7f29\uff0c\u76f4\u5230\u91cd\u590d\u6d88\u9664\u3002<\/p>\n

\n

\u89e3\u6cd5\u4e00\uff1a\u54c8\u5e0c\u96c6\u5408\uff08\u76f4\u89c2\u7248\uff09<\/h4>\n
\n
\n
<\/div>\n<\/div>\n
cpp<\/div>\n
\n
int lengthOfLongestSubstring(string s) {\r\n    unordered_set<char> window;\r\n    int left = 0, ans = 0;\r\n\r\n    for (int right = 0; right < s.size(); right++) {\r\n        \/\/ \u5982\u679c\u53f3\u8fb9\u65b0\u5b57\u7b26\u5df2\u5728\u7a97\u53e3\u4e2d\uff0c\u6301\u7eed\u6536\u7f29\u5de6\u8fb9\r\n        while (window.count(s[right])) {\r\n            window.erase(s[left]);\r\n            left++;\r\n        }\r\n        window.insert(s[right]);\r\n        ans = max(ans, right - left + 1);\r\n    }\r\n    return ans;\r\n}<\/pre>\n
 <\/p>\n<\/div>\n<\/div>\n
    \n
  • \u65f6\u95f4 O(n)\uff0c\u7a7a\u95f4 O(\u2223\u03a3\u2223)\uff08\u5b57\u7b26\u96c6\u5927\u5c0f\uff0c\u6700\u591a 128\uff09<\/li>\n
  • right<\/code> \u548c left<\/code> \u5408\u8ba1\u6700\u591a\u5404\u8d70 n \u6b65\uff0c\u6240\u4ee5\u662f O(n) \u800c\u975e O(n\u00b2)<\/li>\n<\/ul>\n
    \n
    \u89e3\u6cd5\u4e8c\uff1a\u54c8\u5e0c\u8868\u8bb0\u5f55\u4e0b\u6807\uff08\u6700\u4f18\uff0c\u4e00\u6b65\u5230\u4f4d\u8df3\u8dc3\uff09\u2b50<\/h4>\n
    \u4e0a\u9762\u7684\u89e3\u6cd5\u5728\u9047\u5230\u91cd\u590d\u65f6\u8981\u4e00\u6b65\u6b65\u79fb\u52a8 left<\/code>\u3002\u7528\u54c8\u5e0c\u8868\u8bb0\u5f55\u6bcf\u4e2a\u5b57\u7b26\u4e0a\u6b21\u51fa\u73b0\u7684\u4f4d\u7f6e<\/strong>\uff0c\u53ef\u4ee5\u8ba9 left<\/code> \u76f4\u63a5\u8df3\u8fc7\u53bb\uff0c\u7701\u53bb while \u5faa\u73af\u3002<\/p>\n
    \n
    \n
    <\/div>\n<\/div>\n
    cpp<\/div>\n
    \n
    int lengthOfLongestSubstring(string s) {\r\n    unordered_map<char, int> last_pos; \/\/ \u5b57\u7b26 -> \u4e0a\u6b21\u51fa\u73b0\u7684\u4e0b\u6807\r\n    int left = 0, ans = 0;\r\n\r\n    for (int right = 0; right < s.size(); right++) {\r\n        char c = s[right];\r\n        \/\/ \u5982\u679c c \u4e4b\u524d\u51fa\u73b0\u8fc7\uff0c\u4e14\u5728\u7a97\u53e3\u5185\uff08>= left\uff09\uff0c\u5219\u76f4\u63a5\u8df3\u8dc3\r\n        if (last_pos.count(c) && last_pos[c] >= left) {\r\n            left = last_pos[c] + 1;\r\n        }\r\n        last_pos[c] = right;\r\n        ans = max(ans, right - left + 1);\r\n    }\r\n    return ans;\r\n}<\/pre>\n
     <\/p>\n<\/div>\n<\/div>\n
    \u5173\u952e\u5728 last_pos[c] >= left<\/code> \u8fd9\u4e2a\u5224\u65ad\u2014\u2014\u5982\u679c\u4e0a\u6b21\u51fa\u73b0\u7684\u4f4d\u7f6e\u5df2\u7ecf\u5728\u7a97\u53e3\u5de6\u8fb9\u4e4b\u5916\uff0c\u8bf4\u660e\u5b83\u4e0d\u5f71\u54cd\u5f53\u524d\u7a97\u53e3\uff0c\u4e0d\u9700\u8981\u79fb\u52a8 left<\/code>\u3002<\/p>\n
    \n
    \u89e3\u6cd5\u4e09\uff1a\u6570\u7ec4\u4ee3\u66ff\u54c8\u5e0c\u8868\uff08\u6781\u81f4\u4f18\u5316\uff09<\/h4>\n
    \u5982\u679c\u5b57\u7b26\u96c6\u662f ASCII\uff08128\u4e2a\uff09\uff0c\u7528\u6570\u7ec4\u6bd4 unordered_map<\/code> \u66f4\u5feb\uff0c\u907f\u514d\u54c8\u5e0c\u8ba1\u7b97\u5f00\u9500\uff1a<\/p>\n
    \n
    \n
    <\/div>\n<\/div>\n
    cpp<\/div>\n
    \n
    int lengthOfLongestSubstring(string s) {\r\n    int last_pos[128];\r\n    fill(last_pos, last_pos + 128, -1); \/\/ \u521d\u59cb\u5316\u4e3a -1 \u8868\u793a\u672a\u51fa\u73b0\r\n    int left = 0, ans = 0;\r\n\r\n    for (int right = 0; right < s.size(); right++) {\r\n        int c = s[right];\r\n        if (last_pos[c] >= left) {\r\n            left = last_pos[c] + 1;\r\n        }\r\n        last_pos[c] = right;\r\n        ans = max(ans, right - left + 1);\r\n    }\r\n    return ans;\r\n}<\/pre>\n
     <\/p>\n<\/div>\n<\/div>\n
    \u5b9e\u6218\u4e2d\u8fd9\u7248\u6700\u5feb\uff0c\u5e38\u6570\u56e0\u5b50\u6700\u5c0f\u3002<\/p>\n
    \n
    \u4e09\u79cd\u89e3\u6cd5\u5bf9\u6bd4<\/h4>\n
    \n\n\n\n\n\n\n\n
    \u89e3\u6cd5<\/th>\n\u65f6\u95f4<\/th>\n\u7a7a\u95f4<\/th>\n\u7279\u70b9<\/th>\n<\/tr>\n<\/thead>\n
    \u54c8\u5e0c\u96c6\u5408 + while<\/td>\nO(n)<\/td>\nO(|\u03a3|)<\/td>\n\u6700\u76f4\u89c2\uff0c\u9002\u5408\u8bb2\u601d\u8def<\/td>\n<\/tr>\n
    \u54c8\u5e0c\u8868\u8bb0\u5f55\u4e0b\u6807<\/strong><\/td>\nO(n)<\/strong><\/td>\nO(|\u03a3|)<\/strong><\/td>\n\u9762\u8bd5\u63a8\u8350\uff0c\u903b\u8f91\u6700\u6e05\u6670<\/strong><\/td>\n<\/tr>\n
    \u6570\u7ec4\u4ee3\u66ff\u54c8\u5e0c<\/td>\nO(n)<\/td>\nO(128)<\/td>\n\u6027\u80fd\u6700\u4f73\uff0c\u7ade\u8d5b\u5e38\u7528<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
    \n
    \u4e24\u9053\u9898\u7684\u5171\u540c\u6a21\u5f0f<\/h4>\n
    \u63a5\u96e8\u6c34\u548c\u8fd9\u9053\u9898\uff0c\u4e00\u4e2a\u7528\u53cc\u6307\u9488\u4ece\u4e24\u7aef\u5f80\u4e2d\u95f4<\/strong>\uff0c\u4e00\u4e2a\u7528\u6ed1\u52a8\u7a97\u53e3\u4ece\u5de6\u5f80\u53f3<\/strong>\uff0c\u90fd\u662f O(n) \u641e\u5b9a\u770b\u4f3c\u9700\u8981 O(n\u00b2) \u7684\u95ee\u9898\u3002<\/p>\n
    \u9762\u8bd5\u65f6\u628a”\u4e3a\u4ec0\u4e48\u4e0d\u7528\u66b4\u529b”\u548c”\u7a97\u53e3\u6536\u7f29\u7684\u6b63\u786e\u6027”\u8bb2\u6e05\u695a\uff0c\u6bd4\u76f4\u63a5\u80cc\u4ee3\u7801\u66f4\u80fd\u62ff\u5230\u9ad8\u5206\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
    \u529b\u6263\u7b2c 3 \u9898\u3002\u627e\u51fa\u4e00\u4e2a\u5b57\u7b26\u4e32\u4e2d\uff0c\u4e0d\u542b\u91cd<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[24],"tags":[],"class_list":["post-7381","post","type-post","status-publish","format-standard","hentry","category-value_docs"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7381","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=7381"}],"version-history":[{"count":1,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7381\/revisions"}],"predecessor-version":[{"id":7382,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7381\/revisions\/7382"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=7381"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=7381"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=7381"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}