{"id":1858,"date":"2016-03-05T23:45:51","date_gmt":"2016-03-05T15:45:51","guid":{"rendered":"http:\/\/boweihe.me\/?p=1858"},"modified":"2016-03-05T23:45:51","modified_gmt":"2016-03-05T15:45:51","slug":"leetcode-15-3sum","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=1858","title":{"rendered":"LeetCode 15. 3Sum"},"content":{"rendered":"<p><strong>\u539f\u9898\uff1a<\/strong><a href=\"https:\/\/leetcode.com\/problems\/3sum\/\" target=\"_blank\" rel=\"noopener noreferrer\">https:\/\/leetcode.com\/problems\/3sum\/<\/a><br \/>\n<strong>\u601d\u8def\uff1a<\/strong><br \/>\n3Sum\u7684\u95ee\u9898\u5176\u5b9e\u662f2Sum\u95ee\u9898\u7684\u664b\u7ea7\u7248\uff0c\u53ef\u6211\u5f53\u5e74\u6295\u673a\u53d6\u5de7\u7528hashmap\u8fc7\u4e862sum\u95ee\u9898\uff08\u6709\u5174\u8da3\u53ef\u4ee5\u641c\u4e0b\u6211\u7684\u89e3\u6cd5^-^\uff09\uff0c\u5bfc\u81f4\u8fd9\u4e2a3sum\u5361\u58f3\u4e86\u5f88\u4e45\u3002\u6240\u4ee5\u7ecf\u9a8c\u6559\u8bad\u662f\uff0c<span style=\"color: #ff6600;\">\u4e0d\u7ba1\u81ea\u5df1AC\u4e86\u6ca1\u6709\uff0c\u8981\u770b\u770b\u522b\u4eba\u600e\u4e48\u505a\u7684\uff0c\u6b6a\u95e8\u90aa\u9053\u4e0d\u4e00\u5b9a\u6b21\u6b21\u901a\u7528\u3002<\/span><br \/>\n\u56e0\u6b64\u5148\u6765\u89e3\u51b3\u4e0b2sum\u7684\u95ee\u9898\uff0c\u4e5f\u5c31\u662f\u7ed9\u5b9a\u4e00\u4e2a\u6570\u7ec4\uff0c\u627e\u5230\u4e24\u4e2a\u5143\u7d20a[i],a[j]\u4f7f\u5f97a[i]+a[j]=X\u7684\u95ee\u9898\uff0c\u7b80\u5355\u70b9\uff0c\u5047\u8bbeX=0\uff1b\u8fd9\u4e2a\u95ee\u9898\u53ef\u4ee5\u7528\u4e24\u4e2a\u6307\u9488\u6765\u89e3\u51b3\uff0c\u5f53\u7136\u524d\u63d0\u662f\u8981\u5148\u628a\u6570\u7ec4\u6392\u5e8f\u597d\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(nlogn). \u6392\u5e8f\u540e\uff0c\u5047\u8bbe\u4e24\u4e2a\u6307\u9488\u4e00\u5f00\u59cb\u6307\u5411\u6570\u7ec4\u7684\u5934\u3001\u672b\u5143\u7d20(i=0, j=size-1)\uff0c\u7136\u540e\u5c31\u6709\u4e09\u79cd\u53ef\u80fd\u6027\uff1a<\/p>\n<ul>\n<li>\u521a\u597d\u78b0\u5de7\u8fd9\u4e24\u4e2a\u503c\u7684\u548c\u5c31\u662f0 \uff0c\u90a3\u4e48\u4e0b\u4e00\u6b65i,j\u5c31\u8981\u5404\u81ea\u671d\u5411\u5185\u90e8\u79fb\u52a8\u4e00\u683c(i++, j&#8211;)\u3002\u8fd9\u91cc\u4e0d\u4f1a\u4ea7\u751f\u5206\u652f\u60c5\u51b5\uff0c\u5373\u4e0d\u53ef\u80fd\u5b58\u5728a[i]+a[j] == a[i+1]+a[j] \u6216==a[i]+a[j-1]\uff0c\u9664\u975e\u524d\u9879\u3001\u540e\u9879\u7684\u503c\u662f\u540c\u4e00\u4e2a\u5143\u7d20\uff1b<\/li>\n<li>\u5982\u679c\u4e24\u4e2a\u503c\u7684\u548c&lt;0\u4e86\uff0c\u90a3\u8bf4\u660e\u8d1f\u80fd\u91cf\u592a\u5927\u4e86\uff0c\u56e0\u6b64i\u660e\u663e\u592a\u5c0f\u4e86\uff0c\u8981\u628ai\u5411\u53f3\u79fb\u52a8\u8ba9\u5b83\u53d8\u5927\u624d\u6709\u53ef\u80fd\uff0c\u56e0\u6b64i++\uff1b<\/li>\n<li>\u4e0e\u4e0a\u4e00\u6761\u540c\u7406\uff0cj&#8211;;<\/li>\n<\/ul>\n<p>\u6240\u4ee5\uff0c2sum\u95ee\u9898\u5728\u6392\u5e8f\u540e\uff0c\u5185\u90e8\u67e5\u627e\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662f\u7ebf\u6027\u590d\u6742\u5ea6O(n).<br \/>\n\u90a3\u4e483sum\u95ee\u9898\u5462\uff0c\u53ef\u4ee5\u5148\u7b80\u5316\u4e00\u4e0b\uff0c\u5047\u8bbe\u4e0d\u7528\u8003\u8651\u6570\u7ec4\u5185\u6709\u91cd\u590d\u5143\u7d20\u7684\u60c5\u51b5\uff0c\u90a3\u4e48\u53ef\u4ee5\u628a3Sum\u95ee\u9898\u8fd9\u6837\u7b80\u5316\uff0c\u56fa\u5b9a\u4e00\u4e2a\u4f4d\u7f6e\u7684\u5143\u7d20a[pos]\uff0c\u5728\u6570\u7ec4\u5185\u5bfb\u627e\u53e6\u5916\u4e24\u4e2a\u5143\u7d20\uff0c\u5176\u503ca[i]+a[j]==-a[pos]\uff0c\u8fd9\u5c31\u53d8\u62102Sum\u95ee\u9898\u4e86\uff0c\u5176\u4e2d\u4e4b\u524d\u63d0\u5230\u7684X=-a[pos]\u3002\u6574\u4e2a\u7b97\u6cd5\u9700\u8981\u5148\u6392\u5e8f\u4e00\u904d\uff0c\u65f6\u95f4\u590d\u6742\u5ea6O(nlogn)\uff0c\u7136\u540e\u9700\u8981\u904d\u5386\u6bcf\u4e2apos\u518d\u5728\u5faa\u73af\u91cc\u505a2Sum\u95ee\u9898\uff0c\u590d\u6742\u5ea6\u4e3aO(n^2)\uff0c\u6240\u4ee5\u4e24\u4e2a\u8fde\u5728\u4e00\u8d77\uff0c\u590d\u6742\u5ea6\u5728O(n^2)\u8303\u56f4\u5185\uff08\u66b4\u529b\u89e3\u6cd5\u590d\u6742\u5ea6\u4e3aO(n^3)\uff09\u3002<br \/>\n<strong>\u4ee3\u7801\uff08\u8bb0\u5f97\u5904\u7406\u91cd\u590d\u95ee\u9898\uff09<\/strong>\uff1a<\/p>\n<pre class=\"lang:c++ decode:true \">bool sortFunc (int i,int j) { return (i&lt;j); }\nclass Solution {\npublic:\n    vector&lt;vector&lt;int&gt;&gt; threeSum(vector&lt;int&gt;&amp; nums) {\n        sort(nums.begin(), nums.end(), sortFunc);\n        vector&lt;vector&lt;int&gt;&gt; results;\n        for(int pos=0; pos&lt;nums.size(); pos++){\n            threeSumSub(nums, pos, results);\n            while(pos+1 &lt; nums.size() &amp;&amp; nums[pos+1] == nums[pos])\n                pos++;\n        };\n        return results;\n    }\n    void threeSumSub(vector&lt;int&gt;&amp; nums, int pos, vector&lt;vector&lt;int&gt;&gt; &amp;results) {\n        \/\/Find two elements which add up equals -nums[pos]\n        int i = pos+1;\n        int j = nums.size() - 1;\n        int val;\n        while(i &lt; j) {\n            val = nums[pos] + nums[i] + nums[j];\n            if(val == 0){\n                vector&lt;int&gt; solution;\n                solution.push_back(nums[pos]);\n                solution.push_back(nums[i]);\n                solution.push_back(nums[j]);\n                results.push_back(solution);\n                while(nums[i+1] == nums[i] &amp;&amp; i &lt; j) i++;\n                while(nums[j-1] == nums[j] &amp;&amp; i &lt; j) j--;\n                i++;\n                j--;\n            } else if (val &lt; 0) {\n                \/\/Too big, move right\n                while(nums[i+1] == nums[i] &amp;&amp; i &lt; j) i++;\n                i++;\n            } else {\n                while(nums[j-1] == nums[j] &amp;&amp; i &lt; j) j--;\n                j--;\n            }\n        }\n    }\n};<\/pre>\n<p>&nbsp;<br \/>\n&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u539f\u9898\uff1ahttps:\/\/leetcode.com\/problems\/3sum\/ \u601d\u8def\uff1a 3Sum\u7684\u95ee\u9898\u5176\u5b9e\u662f2Sum\u95ee\u9898\u7684\u664b\u7ea7\u7248\uff0c\u53ef\u6211\u5f53\u5e74\u6295\u673a\u53d6\u5de7\u7528hashmap\u8fc7\u4e862sum\u95ee\u9898\uff08\u6709\u5174\u8da3\u53ef\u4ee5\u641c\u4e0b\u6211\u7684\u89e3\u6cd5^-^\uff09\uff0c\u5bfc\u81f4\u8fd9\u4e2a3sum\u5361\u58f3\u4e86\u5f88\u4e45\u3002\u6240\u4ee5\u7ecf\u9a8c\u6559\u8bad\u662f\uff0c\u4e0d\u7ba1\u81ea\u5df1AC\u4e86\u6ca1\u6709\uff0c\u8981\u770b\u770b\u522b\u4eba\u600e\u4e48\u505a\u7684\uff0c\u6b6a\u95e8\u90aa\u9053\u4e0d\u4e00\u5b9a\u6b21\u6b21\u901a\u7528\u3002 \u56e0\u6b64\u5148\u6765\u89e3\u51b3\u4e0b2sum\u7684\u95ee\u9898\uff0c\u4e5f\u5c31\u662f\u7ed9\u5b9a\u4e00\u4e2a\u6570\u7ec4\uff0c\u627e\u5230\u4e24\u4e2a\u5143\u7d20a[i],a[j]\u4f7f\u5f97a[i]+a[j]=X\u7684\u95ee\u9898\uff0c\u7b80\u5355\u70b9\uff0c\u5047\u8bbeX=0\uff1b\u8fd9\u4e2a\u95ee\u9898\u53ef\u4ee5\u7528\u4e24\u4e2a\u6307\u9488\u6765\u89e3\u51b3\uff0c\u5f53\u7136\u524d\u63d0\u662f\u8981\u5148\u628a\u6570\u7ec4\u6392\u5e8f\u597d\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(nlogn). \u6392\u5e8f\u540e\uff0c\u5047\u8bbe\u4e24\u4e2a\u6307\u9488\u4e00\u5f00\u59cb\u6307\u5411\u6570\u7ec4\u7684\u5934\u3001\u672b\u5143\u7d20(i=0, j=size-1)\uff0c\u7136\u540e\u5c31\u6709\u4e09\u79cd\u53ef\u80fd\u6027\uff1a \u521a\u597d\u78b0\u5de7\u8fd9\u4e24\u4e2a\u503c\u7684\u548c\u5c31\u662f0 \uff0c\u90a3\u4e48\u4e0b\u4e00\u6b65i,j\u5c31\u8981\u5404\u81ea\u671d\u5411\u5185\u90e8\u79fb\u52a8\u4e00\u683c(i++, j&#8211;)\u3002\u8fd9\u91cc\u4e0d\u4f1a\u4ea7\u751f\u5206\u652f\u60c5\u51b5\uff0c\u5373\u4e0d\u53ef\u80fd\u5b58\u5728a[i]+a[j] == a[i+1]+a[j] \u6216==a[i]+a[j-1]\uff0c\u9664\u975e\u524d\u9879\u3001\u540e\u9879\u7684\u503c\u662f\u540c\u4e00\u4e2a\u5143\u7d20\uff1b \u5982\u679c\u4e24\u4e2a\u503c\u7684\u548c&lt;0\u4e86\uff0c\u90a3\u8bf4\u660e\u8d1f\u80fd\u91cf\u592a\u5927\u4e86\uff0c\u56e0\u6b64i\u660e\u663e\u592a\u5c0f\u4e86\uff0c\u8981\u628ai\u5411\u53f3\u79fb\u52a8\u8ba9\u5b83\u53d8\u5927\u624d\u6709\u53ef\u80fd\uff0c\u56e0\u6b64i++\uff1b \u4e0e\u4e0a\u4e00\u6761\u540c\u7406\uff0cj&#8211;; \u6240\u4ee5\uff0c2sum\u95ee\u9898\u5728\u6392\u5e8f\u540e\uff0c\u5185\u90e8\u67e5\u627e\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662f\u7ebf\u6027\u590d\u6742\u5ea6O(n). \u90a3\u4e483sum\u95ee\u9898\u5462\uff0c\u53ef\u4ee5\u5148\u7b80\u5316\u4e00\u4e0b\uff0c\u5047\u8bbe\u4e0d\u7528\u8003\u8651\u6570\u7ec4\u5185\u6709\u91cd\u590d\u5143\u7d20\u7684\u60c5\u51b5\uff0c\u90a3\u4e48\u53ef\u4ee5\u628a3Sum\u95ee\u9898\u8fd9\u6837\u7b80\u5316\uff0c\u56fa\u5b9a\u4e00\u4e2a\u4f4d\u7f6e\u7684\u5143\u7d20a[pos]\uff0c\u5728\u6570\u7ec4\u5185\u5bfb\u627e\u53e6\u5916\u4e24\u4e2a\u5143\u7d20\uff0c\u5176\u503ca[i]+a[j]==-a[pos]\uff0c\u8fd9\u5c31\u53d8\u62102Sum\u95ee\u9898\u4e86\uff0c\u5176\u4e2d\u4e4b\u524d\u63d0\u5230\u7684X=-a[pos]\u3002\u6574\u4e2a\u7b97\u6cd5\u9700\u8981\u5148\u6392\u5e8f\u4e00\u904d\uff0c\u65f6\u95f4\u590d\u6742\u5ea6O(nlogn)\uff0c\u7136\u540e\u9700\u8981\u904d\u5386\u6bcf\u4e2apos\u518d\u5728\u5faa\u73af\u91cc\u505a2Sum\u95ee\u9898\uff0c\u590d\u6742\u5ea6\u4e3aO(n^2)\uff0c\u6240\u4ee5\u4e24\u4e2a\u8fde\u5728\u4e00\u8d77\uff0c\u590d\u6742\u5ea6\u5728O(n^2)\u8303\u56f4\u5185\uff08\u66b4\u529b\u89e3\u6cd5\u590d\u6742\u5ea6\u4e3aO(n^3)\uff09\u3002 \u4ee3\u7801\uff08\u8bb0\u5f97\u5904\u7406\u91cd\u590d\u95ee\u9898\uff09\uff1a bool sortFunc (int i,int j) { return (i&lt;j); } class Solution { public: vector&lt;vector&lt;int&gt;&gt; threeSum(vector&lt;int&gt;&amp; nums) { sort(nums.begin(), nums.end(), sortFunc); vector&lt;vector&lt;int&gt;&gt; results; for(int pos=0; pos&lt;nums.size(); pos++){ threeSumSub(nums, pos, results); while(pos+1 &lt; nums.size() &amp;&amp; nums[pos+1] == nums[pos]) pos++; }; [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[66],"class_list":["post-1858","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1858","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1858"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1858\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1858"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1858"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1858"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}