{"id":2394,"date":"2022-01-26T09:47:14","date_gmt":"2022-01-26T01:47:14","guid":{"rendered":"http:\/\/139.9.1.231\/?p=2394"},"modified":"2022-01-26T09:47:15","modified_gmt":"2022-01-26T01:47:15","slug":"leetcodeday76","status":"publish","type":"post","link":"http:\/\/139.9.1.231\/index.php\/2022\/01\/26\/leetcodeday76\/","title":{"rendered":"leetcodeday76&#8211;\u6700\u5c0f\u8986\u76d6\u5b50\u4e32"},"content":{"rendered":"\n<p>\u7ed9\u4f60\u4e00\u4e2a\u5b57\u7b26\u4e32&nbsp;<code>s<\/code>&nbsp;\u3001\u4e00\u4e2a\u5b57\u7b26\u4e32&nbsp;<code>t<\/code>&nbsp;\u3002\u8fd4\u56de&nbsp;<code>s<\/code>&nbsp;\u4e2d\u6db5\u76d6&nbsp;<code>t<\/code>&nbsp;\u6240\u6709\u5b57\u7b26\u7684\u6700\u5c0f\u5b50\u4e32\u3002\u5982\u679c&nbsp;<code>s<\/code>&nbsp;\u4e2d\u4e0d\u5b58\u5728\u6db5\u76d6&nbsp;<code>t<\/code>&nbsp;\u6240\u6709\u5b57\u7b26\u7684\u5b50\u4e32\uff0c\u5219\u8fd4\u56de\u7a7a\u5b57\u7b26\u4e32&nbsp;<code>\"\"<\/code>&nbsp;\u3002<\/p>\n\n\n\n<p><strong>\u6ce8\u610f\uff1a<\/strong><\/p>\n\n\n\n<ul><li>\u5bf9\u4e8e&nbsp;<code>t<\/code>&nbsp;\u4e2d\u91cd\u590d\u5b57\u7b26\uff0c\u6211\u4eec\u5bfb\u627e\u7684\u5b50\u5b57\u7b26\u4e32\u4e2d\u8be5\u5b57\u7b26\u6570\u91cf\u5fc5\u987b\u4e0d\u5c11\u4e8e&nbsp;<code>t<\/code>&nbsp;\u4e2d\u8be5\u5b57\u7b26\u6570\u91cf\u3002<\/li><li>\u5982\u679c&nbsp;<code>s<\/code>&nbsp;\u4e2d\u5b58\u5728\u8fd9\u6837\u7684\u5b50\u4e32\uff0c\u6211\u4eec\u4fdd\u8bc1\u5b83\u662f\u552f\u4e00\u7684\u7b54\u6848\u3002<\/li><\/ul>\n\n\n\n<p><strong>\u793a\u4f8b 1\uff1a<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><strong>\u8f93\u5165\uff1a<\/strong>s = \"ADOBECODEBANC\", t = \"ABC\"\n<strong>\u8f93\u51fa\uff1a<\/strong>\"BANC\"<\/code><\/pre>\n\n\n\n<p><strong>\u793a\u4f8b 2\uff1a<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><strong>\u8f93\u5165\uff1a<\/strong>s = \"a\", t = \"a\"\n<strong>\u8f93\u51fa\uff1a<\/strong>\"a\"<\/code><\/pre>\n\n\n\n<p><strong>\u793a\u4f8b 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><strong>\u8f93\u5165:<\/strong> s = \"a\", t = \"aa\"\n<strong>\u8f93\u51fa:<\/strong> \"\"\n<strong>\u89e3\u91ca:<\/strong> t \u4e2d\u4e24\u4e2a\u5b57\u7b26 'a' \u5747\u5e94\u5305\u542b\u5728 s \u7684\u5b50\u4e32\u4e2d\uff0c\n\u56e0\u6b64\u6ca1\u6709\u7b26\u5408\u6761\u4ef6\u7684\u5b50\u5b57\u7b26\u4e32\uff0c\u8fd4\u56de\u7a7a\u5b57\u7b26\u4e32\u3002<\/code><\/pre>\n\n\n\n<p><strong>\u63d0\u793a\uff1a<\/strong><\/p>\n\n\n\n<ul><li><code>1 &lt;= s.length, t.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>s<\/code>&nbsp;\u548c&nbsp;<code>t<\/code>&nbsp;\u7531\u82f1\u6587\u5b57\u6bcd\u7ec4\u6210<\/li><\/ul>\n\n\n\n<p><strong>\u8fdb\u9636\uff1a<\/strong>\u4f60\u80fd\u8bbe\u8ba1\u4e00\u4e2a\u5728&nbsp;<code>o(n)<\/code>&nbsp;\u65f6\u95f4\u5185\u89e3\u51b3\u6b64\u95ee\u9898\u7684\u7b97\u6cd5\u5417\uff1f<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code># @lc app=leetcode.cn id=76 lang=python3\r\n#\r\n# &#91;76] \u6700\u5c0f\u8986\u76d6\u5b50\u4e32\r\n#\r\n#\u6ed1\u52a8\u7a97\u53e3\u65b9\u6cd5\r\n# @lc code=start\r\nclass Solution:\r\n    def minWindow(self, s: str, t: str) -> str:\r\n        dict1=dict()\r\n        for i in t:\r\n            if i in dict1:\r\n                dict1&#91;i]+=1\r\n            else:\r\n                dict1&#91;i]=1\r\n        def isempty(dicts):\r\n            for i in dicts:\r\n                if dicts&#91;i]>0:\r\n                    return False\r\n            return True\r\n        if len(t)==1:\r\n            if t in s:return t\r\n            else: return \"\"\r\n        j=-1\r\n        i=0\r\n        m=i\r\n        n=j\r\n        lens= 10**5\r\n        while  i&lt;=len(s)-len(t):\r\n            if isempty(dict1):\r\n                if j-i+1&lt;lens:\r\n                    lens=j-i+1\r\n                    m=i\r\n                    n=j\r\n                if s&#91;i] in dict1:\r\n                    dict1&#91;s&#91;i]]= dict1&#91;s&#91;i]]+1\r\n                i=i+1\r\n            elif j&lt;len(s)-1:\r\n                j=j+1\r\n                if s&#91;j] in dict1 :\r\n                    dict1&#91;s&#91;j]]=dict1&#91;s&#91;j]]-1  \r\n            elif j==len(s)-1:\r\n                i=i+1             \r\n                    \r\n        if lens == 10**5:\r\n            return \"\"\r\n        else: return s&#91;m:n+1]<\/code><\/pre>\n\n\n\n<figure class=\"wp-block-image size-full is-style-default\"><img loading=\"lazy\" width=\"756\" height=\"253\" src=\"http:\/\/139.9.1.231\/wp-content\/uploads\/2022\/01\/image-293.png\" alt=\"\" class=\"wp-image-2395\" srcset=\"http:\/\/139.9.1.231\/wp-content\/uploads\/2022\/01\/image-293.png 756w, http:\/\/139.9.1.231\/wp-content\/uploads\/2022\/01\/image-293-300x100.png 300w\" sizes=\"(max-width: 756px) 100vw, 756px\" \/><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>\u7ed9\u4f60\u4e00\u4e2a\u5b57\u7b26\u4e32&nbsp;s&nbsp;\u3001\u4e00\u4e2a\u5b57\u7b26\u4e32&nbsp;t&nbsp;\u3002\u8fd4\u56de&nbsp;s&nbsp; &hellip; <a href=\"http:\/\/139.9.1.231\/index.php\/2022\/01\/26\/leetcodeday76\/\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">leetcodeday76&#8211;\u6700\u5c0f\u8986\u76d6\u5b50\u4e32<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[6],"tags":[],"_links":{"self":[{"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/posts\/2394"}],"collection":[{"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/comments?post=2394"}],"version-history":[{"count":1,"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/posts\/2394\/revisions"}],"predecessor-version":[{"id":2396,"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/posts\/2394\/revisions\/2396"}],"wp:attachment":[{"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/media?parent=2394"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/categories?post=2394"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/139.9.1.231\/index.php\/wp-json\/wp\/v2\/tags?post=2394"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}