{"id":903,"date":"2017-11-23T00:14:13","date_gmt":"2017-11-23T08:14:13","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=903"},"modified":"2018-08-16T07:35:15","modified_gmt":"2018-08-16T14:35:15","slug":"leetcode-1-two-sum","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1-two-sum\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1. Two Sum"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1. Two Sum - \u5237\u9898\u627e\u5de5\u4f5c EP1\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/tNtk_rwbaIk?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>Given an array of integers, return\u00a0<b>indices<\/b>\u00a0of the two numbers such that they add up to a specific target.<\/p>\n<p>You may assume that each input would have\u00a0<b><i>exactly<\/i><\/b>\u00a0one solution, and you may not use the\u00a0<i>same<\/i>\u00a0element twice.<\/p>\n<p><b>Example:<\/b><\/p>\n<pre class=\"crayon:false\">Given nums = [2, 7, 11, 15], target = 9,\r\n\r\nBecause nums[<b>0<\/b>] + nums[<b>1<\/b>] = 2 + 7 = 9,\r\nreturn [<b>0<\/b>, <b>1<\/b>].<\/pre>\n<p><strong>Idea:<\/strong><\/p>\n<p>Brute force \/ Hashtable<\/p>\n<p><strong>Solution1:<\/strong><\/p>\n<p>Brute force \/ C++<\/p>\n<p>Time complexity: O(n^2)<\/p>\n<p>Space complexity: O(1)<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 166 ms\r\nclass Solution {\r\npublic:\r\n  vector&lt;int&gt; twoSum(vector&lt;int&gt;&amp; nums, int target) {\r\n    for (int i = 0; i &lt; nums.size(); ++i) {\r\n      for (int j = i + 1;j &lt; nums.size(); ++j) {\r\n        int sum = nums[i] + nums[j];\r\n        if (sum == target) {\r\n          return {i, j};\r\n        }\r\n      }\r\n    }\r\n    return {};\r\n  }\r\n};<\/pre>\n<p><strong>Solution 2:<\/strong><\/p>\n<p>Hashtable \/ C++<\/p>\n<p>Time complexity: O(n)<\/p>\n<p>Space complexity: O(n)<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 6 ms\r\nclass Solution {\r\npublic:\r\n  vector&lt;int&gt; twoSum(vector&lt;int&gt;&amp; nums, int target) {\r\n    unordered_map&lt;int, int&gt; indies;\r\n    for (int i = 0; i &lt; nums.size(); ++i)\r\n      indies[nums[i]] = i;\r\n    \r\n    for (int i = 0; i &lt; nums.size(); ++i) {\r\n      int left = target - nums[i];\r\n      if (indies.count(left) &amp;&amp; indies[left] != i) {\r\n          return {i, indies[left]};\r\n      }\r\n    }\r\n    return {};\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem: Given an array of integers, return\u00a0indices\u00a0of the two numbers such that they add up to a specific target. You may assume that each input&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[163,70],"tags":[222,82,148,62],"class_list":["post-903","post","type-post","status-publish","format-standard","hentry","category-easy","category-hashtable","tag-easy","tag-hashtable","tag-pair","tag-sum","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/903","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=903"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/903\/revisions"}],"predecessor-version":[{"id":3538,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/903\/revisions\/3538"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=903"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=903"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=903"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}