{"id":2791,"date":"2020-01-18T10:22:59","date_gmt":"2020-01-18T02:22:59","guid":{"rendered":"http:\/\/www.sniper97.cn\/?p=2791"},"modified":"2020-01-18T10:22:59","modified_gmt":"2020-01-18T02:22:59","slug":"%e3%80%90leetcode%e3%80%910015-%e4%b8%89%e6%95%b0%e4%b9%8b%e5%92%8c","status":"publish","type":"post","link":"http:\/\/www.sniper97.cn\/index.php\/note\/algorithm\/2791\/","title":{"rendered":"\u3010LeetCode\u30110015 \u4e09\u6570\u4e4b\u548c"},"content":{"rendered":"\n<p><a href=\"https:\/\/leetcode-cn.com\/problems\/3sum\">https:\/\/leetcode-cn.com\/problems\/3sum<\/a><\/p>\n\n\n<p>\u4ee3\u7801:<\/p>\n\n\n<pre class=\"wp-block-preformatted\"># -*- coding:utf-8 -*-\n<em>\n<\/em>class Solution(object):\n    def threeSum(self, nums):\n        <em>\"\"\"\n        <\/em><strong><em>:type<\/em><\/strong><em> nums: List[int]\n        <\/em><strong><em>:rtype<\/em><\/strong><em>: List[List[int]]\n        \"\"\"\n        <\/em>res_temp = []\n        for i in range(len(nums)):\n            temp_list = [0 for _ in range(len(nums))]\n            for j in range(len(temp_list)):\n                if i == j:\n                    temp_list[j] = float('inf')\n                    continue\n                # b = -c -a\n                temp_list[j] = -nums[i] - nums[j]\n            for j in range(len(nums)):\n                for k in range(len(temp_list)):\n                    if nums[j] == temp_list[k] and j != k and i != k and i != j:\n                        temp_res = [nums[i], nums[j], nums[k]]\n                        temp_res.sort()\n                        res_temp.append(temp_res)\n        res = []\n        for each in res_temp:\n            if each not in res:\n                res.append(each)\n        return res\nif __name__ == '__main__':\n    nums = [-1, 0, 1, 2, -1, -4]\n    print(Solution().threeSum1(nums))<\/pre>\n\n\n<p><strong>\u601d\u8def<\/strong>\uff1a\u8fd9\u9053\u9898\u554a\uff0c\u8fd9\u9053\u9898\u53eb\u8089\u86cb\u8471\u51fb\uff08\u4e0d\u662f\uff09\u3002<\/p>\n\n\n<p>\u4e0a\u9762\u7684\u4ee3\u7801\u554a\uff0c\u4e5f\u662f\u4e0d\u80fdAC\u7684\uff0c\u8d85\u65f6\uff0c\u5509\uff0c\u770b\u8bc4\u8bba\u597d\u591a\u90fd\u662f\u8d85\u65f6\u7684\u3002<\/p>\n\n\n<p>\u8fd9\u9053\u9898\u7684\u601d\u8def\u5176\u5b9e\u4e5f\u4e0d\u9ebb\u70e6\uff0c\u505a\u8fc70001\u7684\u57fa\u672c\u90fd\u4f1a\u4e86\uff0c\u65e0\u975e\u662f\u8bbea+b=-c\u7136\u540e\u8ba1\u7b97n\u4e2ac\u7136\u540e\u53bb\u91cd\u5373\u53ef\uff0c\u90a3\u8d85\u65f6\u548b\u529e\u561b\uff0c\u5927\u6982\u53ea\u80fd\u8fc7200\u591a\u4e2a\u7528\u4f8b\u3002<\/p>\n\n\n<p><strong>\u601d\u8003<\/strong>\uff1a\u770b\u4e86\u5927\u4f6c\u7684\u8bc4\u8bba\uff0c\u8fd9\u9053\u9898\u53ef\u4ee5\u7528\u4e24\u4e2a\u6307\u9488\u4ee3\u66ff\u4e24\u4e2afor\uff0c\u518d\u52a0\u4e0a\u6307\u9488\u904d\u5386\u7684for\uff0c\u5b9e\u9645\u4e0a\u6211\u4eec\u7701\u53bb\u4e86\u4e00\u5c42\u5faa\u73af\uff0c\u518d\u914d\u5408\u6bd4\u8f83\u4e25\u683c\u7684\u526a\u679d\uff0c\u65f6\u95f4\u4f1a\u88ab\u538b\u7f29\u7684\u5f88\u5c0f\u3002<\/p>\n\n\n<p>\u601d\u8def\u5b9e\u9645\u4e0a\u5c31\u662f\u5728nums\uff08<strong>\u6392\u5e8f\u597d\u7684<\/strong>\uff09\u5217\u8868\u4e2d\uff0c\u6211\u4eec\u9996\u5148\u9009\u5b9a0\u4f4d\u5143\u7d20\u4e3aa\uff0c\u7136\u540e1\u4f4d\u5143\u7d20\u4e3ab\uff0c-1\u4f4d\u5143\u7d20\u4e3ac\uff0c\u5176\u4e2d\u4e24\u4e2a\u5de6\u53f3\u6307\u9488\u5206\u522b\u6307\u54111\u548c-1\uff0c\u8fd9\u6837\u4e24\u4e2a\u6307\u9488\u4e0d\u65ad\u5411\u5185\u9760\u8fd1\uff0c\u4ee5\u6b64\u8fbe\u5230\u5bf90\u5143\u7d20\u7684\u4e09\u6570\u4e4b\u548c\u7684\u67e5\u627e\u76ee\u7684\u3002<\/p>\n\n\n<p>\u5bf9\u4e8e\u526a\u679d\uff0c\u5982\u679c\u6211\u4eeca+b+b\u5c31\u5927\u4e8e0\u4e86\uff0c\u90a3\u4e48\u5c31\u6ca1\u6709\u5fc5\u8981\u67e5c\u4e86\uff0c\u56e0\u6b64c\u5728b\u7684\u540e\u9762\u6c38\u8fdc\u6bd4\u5f53\u524db\u5927\u3002\u540c\u7406\uff0c\u5f53a+c+c\u5c0f\u4e8e0\u4e5f\u662f\u4e00\u6837\u3002\u8fd8\u6709\u5c31\u662f\u6392\u5e8f\u597d\u7684\u5217\u88680\u53f7\u5143\u7d20\u5927\u4e8e0\uff0c\u90a3\u4e48\u8be5\u5217\u8868\u4e2d\u5fc5\u7136\u4e0d\u5b58\u5728\u4e09\u6570\u4e4b\u548c\u7b49\u4e8e0\u3002<\/p>\n\n\n<p>\u5bf9\u4e8e\u53bb\u91cd\uff0c\u6211\u4eec\u53ea\u9700\u8ba9\u6307\u9488\u8df3\u8fc7\u4e0e\u5f53\u524d\u6570\u5b57\u76f8\u540c\u7684\u7d22\u5f15\u5373\u53ef\uff0c\u7531\u4e8e\u6570\u7ec4\u5df2\u7ecf\u662f\u6392\u5e8f\u8fc7\u7684\uff0c\u8fd9\u4e2a\u64cd\u4f5c\u65e0\u7591\u4e5f\u662f\u5feb\u901f\u7684\u3002<\/p>\n\n\n<pre class=\"wp-block-preformatted\">def threeSum1(self, nums):<br \/>    <em>\"\"\"<br \/><\/em><em>    <\/em><strong><em>:type<\/em><\/strong><em> nums: List[int]<br \/><\/em><em>    <\/em><strong><em>:rtype<\/em><\/strong><em>: List[List[int]]<br \/><\/em><em>    \"\"\"<br \/><\/em><em>    <\/em>res = []<br \/>    nums.sort()<br \/>    for i in range(len(nums) - 2):<br \/>        if nums[i] &gt; 0:  # \u6392\u597d\u5e8f\u4e4b\u540e\uff0c\u5982\u679cnums[i]&gt;0\uff0c\u8bf4\u660e\u540e\u9762\u7684\u6570\u5168\u90e8\u5927\u4e8e0<br \/>            break<br \/>        if i == 0 or nums[i] &gt; nums[i - 1]:  # \u53bb\u91cd<br \/>            left, right = i + 1, len(nums) - 1<br \/>            # \u526a\u679d\uff0c\u4e24\u79cd\u8fb9\u754c\u6761\u4ef6\uff0cb\u503c\u5df2\u7ecf\u8db3\u591f\u5927\uff0c\u5373\u4f7f\u662fb\u548cb\u7684\u4e0b\u4e00\u4f4d\u76f8\u52a0\u90fd\u5927\u4e8e0 \u548cc\u5df2\u7ecf\u8db3\u591f\u5c0f\uff0cc\u548cc\u7684\u524d\u4e00\u4f4d\u76f8\u52a0\u5df2\u7ecf\u5c0f\u4e8e0<br \/>            if nums[i] + nums[left] + nums[left + 1] &gt; 0 or nums[i] + nums[right - 1] + nums[right] &lt; 0:<br \/>                continue<br \/>            while left &lt; right:<br \/>                ident = nums[i] + nums[left] + nums[right]<br \/>                if ident == 0:<br \/>                    res.append([nums[i], nums[left], nums[right]])<br \/>                    left += 1<br \/>                    right -= 1<br \/>                    # \u53bb\u91cd\uff0c\u5c06\u4e0e\u5f53\u524d\u7ed3\u679c\u4e00\u6837\u7684\u6570\u5b57\u5229\u7528\u6307\u9488\u76f4\u63a5\u7b5b\u6389<br \/>                    while left &lt; right and nums[left] == nums[left - 1]:<br \/>                        left += 1<br \/>                    while left &lt; right and nums[right] == nums[right + 1]:<br \/>                        right -= 1<br \/>                elif ident &lt; 0:<br \/>                    left += 1<br \/>                else:<br \/>                    right -= 1<br \/>    return res<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode-cn.com\/problems\/3sum \u4ee3\u7801: # -*- co [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[10],"tags":[],"views":1522,"_links":{"self":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/2791"}],"collection":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/comments?post=2791"}],"version-history":[{"count":0,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/2791\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/media?parent=2791"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/categories?post=2791"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/tags?post=2791"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}