{"id":1762,"date":"2016-02-02T12:22:04","date_gmt":"2016-02-02T04:22:04","guid":{"rendered":"http:\/\/boweihe.me\/?p=1762"},"modified":"2016-02-02T12:22:04","modified_gmt":"2016-02-02T04:22:04","slug":"leetcode-oj-1-two-sum","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=1762","title":{"rendered":"LeetCode OJ #1 Two Sum"},"content":{"rendered":"<p>\u6069\uff0c\u636e\u8bf4\u5237LeetCode\u6bd4\u8f83\u597d\u73a9\uff0c\u4e8e\u662f\u4e4e\u4ece\u7b2c\u4e00\u9898\u5f00\u59cb\u5427\u3002<br \/>\n\u9898\u76ee\uff1a<br \/>\nGiven an array of integers, find two numbers such that they add up to a specific target number.<br \/>\nThe function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.<br \/>\nYou may assume that each input would have exactly one solution.<br \/>\n<b>Input:<\/b> numbers={2, 7, 11, 15}, target=9<br \/>\n<b>Output:<\/b> index1=1, index2=2<br \/>\n\u601d\u8def\uff1a<br \/>\n\u8fd9\u9053\u9898\u7ed9\u7684Hint\u662f\u4e8c\u53c9\u6811\uff0c\u6211\u6709\u70b9\u4e0d\u592a\u61c2\uff0c\u7528\u4e8c\u53c9\u6811\u5b9e\u73b0\u4e86\u4e00\u4e2a\u7248\u672c\uff0c\u4e0d\u8fc7\u4f1a\u8d85\u65f6\u3002\u60f3\u4e86\u4e0b\u8fd8\u662f\u7528map\u7684\u9ed1\u79d1\u6280\u5427\uff0c\u53cd\u6b63\u6ca1\u9650\u5236\u5185\u5b58\u5927\u5c0f\u3002\uff08\u518d\u9ed1\u79d1\u6280\u4e00\u70b9\u53ef\u4ee5\u76f4\u63a5\u7528\u6570\u7ec4\uff0c\u5c31\u662f\u6570\u636e\u591a\u7684\u8bdd\u8981\u627e\u5230\u6700\u5c0f\/\u6700\u5927\u503c\u505a\u597d\u6620\u5c04\uff09<br \/>\n\u4ee3\u7801\uff1a<\/p>\n<pre class=\"lang:c++ decode:true \">class Solution {\nprivate:\n\tmap&lt;int, int&gt; valTable;\npublic:\n\tvector&lt;int&gt; twoSum(vector&lt;int&gt;&amp; nums, int target) {\n\t\tfor (int i = 0; i &lt; nums.size(); i++) {\n\t\t\tint val = nums[i];\n\t\t\tvalTable[val] = i + 1;\n\t\t}\n\t\tfor (int i = 0; i &lt; nums.size(); i++) {\n\t\t\tint ne = target - nums[i];\n\t\t\tmap&lt;int, int&gt;::iterator result = valTable.find(ne);\n\t\t\tif (result != valTable.end()) {\n\t\t\t\tint nextIndex = result-&gt;second;\n\t\t\t\tint currIndex = i + 1;\n\t\t\t\tif (currIndex == nextIndex)\n\t\t\t\t\tcontinue;\n\t\t\t\tvector&lt;int&gt; retIndices;\n\t\t\t\tif (currIndex &gt; nextIndex) {\n\t\t\t\t\tretIndices.push_back(nextIndex);\n\t\t\t\t\tretIndices.push_back(currIndex);\n\t\t\t\t}\n\t\t\t\telse {\n\t\t\t\t\tretIndices.push_back(currIndex);\n\t\t\t\t\tretIndices.push_back(nextIndex);\n\t\t\t\t}\n\t\t\t\treturn retIndices;\n\t\t\t}\n\t\t}\n\t}\n};<\/pre>\n<p>\u8fd0\u884c\u7ed3\u679c\uff1a<br \/>\n\u6211\u53ea\u8d85\u8fc7\u4e8630.19%\u7684\u961f\u53cb\uff0c\u54c8\u54c8~<br \/>\n<a href=\"http:\/\/boweihe.me\/wp-content\/uploads\/2016\/02\/LeetCode_Twp_Sum.jpg\" rel=\"attachment wp-att-1763\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1763\" src=\"http:\/\/boweihe.me\/wp-content\/uploads\/2016\/02\/LeetCode_Twp_Sum.jpg\" alt=\"LeetCode_Twp_Sum\" width=\"1179\" height=\"573\" \/><\/a><br \/>\n&nbsp;<br \/>\n&nbsp;<br \/>\n2018 refined (beats 92.29%):<\/p>\n<pre class=\"lang:c++ decode:true \">class Solution {\npublic:\n    vector&lt;int&gt; twoSum(vector&lt;int&gt;&amp; nums, int target) {\n        unordered_map&lt;int, size_t&gt; num_indices; \/\/ &lt;number, indices&gt;\n        for (size_t i = 0; i &lt; nums.size(); ++i)\n        {\n            auto num = nums[i];\n            if (num_indices.count(target - num) &gt; 0)\n            {\n                return {num_indices[target - num], i};\n            }\n            num_indices[num] = i;\n        }\n        return {-1, -1};\n    }\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u6069\uff0c\u636e\u8bf4\u5237LeetCode\u6bd4\u8f83\u597d\u73a9\uff0c\u4e8e\u662f\u4e4e\u4ece\u7b2c\u4e00\u9898\u5f00\u59cb\u5427\u3002 \u9898\u76ee\uff1a Given an array of integers, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) [&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-1762","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\/1762","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=1762"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1762\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1762"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1762"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1762"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}