{"id":591,"date":"2021-02-10T19:38:09","date_gmt":"2021-02-10T11:38:09","guid":{"rendered":"http:\/\/lonelinerd.com\/?p=591"},"modified":"2021-02-17T14:40:54","modified_gmt":"2021-02-17T06:40:54","slug":"leetcode-1","status":"publish","type":"post","link":"https:\/\/lonelinerd.com\/index.php\/2021\/02\/10\/leetcode-1\/","title":{"rendered":"[LeetCode\u5237\u984c\u7b46\u8a18] 1 – Two Sum"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t
\n\t\t\t\t

\u984c\u76ee\u63cf\u8ff0\uff1a<\/strong><\/span><\/h4>

Given an array of integers, return <\/span>indices<\/span><\/strong><\/span> of the two numbers such that they add up to a specific target.<\/span><\/p>

You may assume that each input would have <\/span>*exactly<\/span>*<\/strong><\/span> one solution, and you may not use the <\/span>same<\/span><\/em><\/span> element twice.<\/span><\/p>

Example:<\/span><\/strong><\/span><\/p>

Given<\/span> nums<\/span> =<\/span> [2<\/span>, 7<\/span>, 11<\/span>, 15<\/span>], target<\/span> =<\/span> 9<\/span>,<\/span>
\u200b<\/span>
Because<\/span> nums<\/span>[0<\/span>] +<\/span> nums<\/span>[1<\/span>] =<\/span> 2<\/span> +<\/span> 7<\/span> =<\/span> 9<\/span>,<\/span>
return<\/span> [0<\/span>, 1<\/span>].<\/span><\/pre>
<\/div>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t
\n\t\t\t\t
\u4e00\u5237\u984c\u89e3\uff08Brute Force\uff09\uff1a<\/strong><\/span><\/h4>
\u00a0 \u00a0 \u00a0 \u00a0 \u9019\u500b\u984c\u7d66\u6211\u5011\u4e00\u500b\u6578\u7d44\uff08arr\uff09\u548c\u4e00\u500b\u76ee\u6a19\u503c\uff08target\uff09\uff0c\u8b93\u6211\u5011\u627e\u51fa\u300c\u552f\u4e00\u300d\u7684\u4e00\u5c0d\u5143\u7d20\u7684\u7d22\u5f15\uff0c\u5b83\u5011\u7684\u548c\u7b49\u65bc\u76ee\u6a19\u503c\u3002\u6700\u7c21\u55ae\u7c97\u66b4\u7684\u65b9\u5f0f\u5c31\u662f\u76f4\u63a5\u5beb\u4e00\u500b\u5d4c\u5957\u5faa\u74b0\u9032\u884c\u904d\u6b77\u3002\u7576\u5916\u5c64\u4e0b\u6a19\u70bai\u6642\uff0c\u5167\u5c64\u5faa\u74b0\u8981\u641c\u7d22\u7684\u76ee\u6a19\u5c31\u662f target – arr[i]\u3002\u5982\u679c\u9019\u4e00\u6b21\u5916\u5c64\u5faa\u74b0\u6c92\u6709\u627e\u5230\uff0c\u5916\u5c64\u4e0b\u6a19+1\uff0c\u5167\u5c64\u4e0b\u6a19\u5247\u59cb\u7d42\u5f9e\u5916\u5c64\u4e0b\u6a19 + 1\u958b\u59cb\u904d\u6b77\u5230\u6578\u7d44\u5c3e\u90e8\u3002<\/p>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t
\n\t\t\t\t
public<\/span> class<\/span> Solution<\/span>{<\/span>
 \u00a0 \u00a0public<\/span> int<\/span>[] TwoSum<\/span>(int<\/span>[] nums<\/span>, int<\/span> target<\/span>){<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0int<\/span> res1<\/span> =<\/span> 0<\/span>;<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0int<\/span> res2<\/span> =<\/span> 0<\/span>;<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0for<\/span>(int<\/span> i<\/span> =<\/span> 0<\/span>; i<\/span> <<\/span> nums<\/span>.Length<\/span>; i<\/span>++<\/span>)<\/span>
 \u00a0 \u00a0 \u00a0  {<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0for<\/span>(int<\/span> j<\/span> =<\/span> i<\/span> +<\/span> 1<\/span>; j<\/span> <<\/span> nums<\/span>.Length<\/span>; j<\/span>++<\/span>)<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  {<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(nums<\/span>[j<\/span>] ==<\/span> target<\/span> -<\/span> nums<\/span>[i<\/span>]){<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0res1<\/span> =<\/span> i<\/span>;<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0res2<\/span> =<\/span> j<\/span>;<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  }<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  }<\/span>
 \u00a0 \u00a0 \u00a0  }<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0return<\/span> int<\/span>[2<\/span>]{res1<\/span>, res2<\/span>};<\/span>
 \u00a0  }<\/span>
}<\/span><\/pre>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t
\n\t\t\t\t
\u4e8c\u5237\u984c\u89e3\uff08Dictionary\uff09\uff1a<\/strong><\/span><\/h4>
\u00a0 \u00a0 \u00a0 \u00a0 \u7531\u65bc\u6211\u5011\u5df2\u7d93\u77e5\u9053\u4e86target\u5fc5\u7136\u662f\u7531\u6578\u7d44\u88e1\u7684\u5169\u500b\u5143\u7d20\u76f8\u52a0\u5f8c\u5f97\u51fa\uff0c\u800c\u9019\u500b\u7d44\u5408\u53c8\u662f\u552f\u4e00\u7684\u3002\u56e0\u6b64\uff0c\u8207\u5176\u7528\u5169\u500b\u5faa\u74b0\u628a\u6240\u6709\u5143\u7d20\u7684\u548c\u90fd\u6aa2\u67e5\u4e00\u904d\uff0c\u4e0d\u5982\u53ea\u7528\u4e00\u500b\u5faa\u74b0\u52a0\u4e00\u500b\u4fdd\u5b58\u6578\u7d44\u7684\u5143\u7d20\u503c\u7684\u5b57\u5178\uff08Key\u662f\u503c\uff0cValue\u662f\u7d22\u5f15\uff09<\/span>\uff0c\u5148\u628a\u7576\u524d\u5143\u7d20\u503c\u8207\u76ee\u6a19\u503c\u4e4b\u9593\u7684\u5dee\u6c42\u51fa\u4f86\uff08target – nums[i]\uff09\uff0c\u7136\u5f8c\u6aa2\u67e5\u4e00\u4e0b\u5b57\u5178\u88e1\u6709\u6c92\u6709\u8207\u9019\u500b\u5dee\u76f8\u7b49\u7684\u503c\uff0c\u5982\u679c\u6709\uff0c\u90a3\u5c31\u4ee3\u8868\u7576\u524d\u7684\u503c\u7684\u7d22\u5f15\uff0c\u9084\u6709\u5b57\u5178\u4e2d\u8207\uff08target – nums[i]\uff09\u76f8\u7b49\u7684Key\u5c0d\u61c9\u7684Value\u5c31\u662f\u6211\u5011\u7684\u7b54\u6848\u3002<\/p>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t
\n\t\t\t\t
public<\/span> class<\/span> Solution<\/span> {<\/span>
 \u00a0 \u00a0public<\/span> int<\/span>[] TwoSum<\/span>(int<\/span>[] nums<\/span>, int<\/span> target<\/span>) {<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0int<\/span>[] res<\/span> =<\/span> new<\/span> int<\/span>[2<\/span>]{-<\/span>1<\/span>, -<\/span>1<\/span>};<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0
<\/span>        \/\/\u4fdd\u5b58\u6578\u7d44\u88ab\u904d\u6b77\u904e\u7684\u503c\uff08Key\uff09\u53ca\u5176\u7d22\u5f15\uff08Value\uff09\u7684\u5b57\u5178
 \u00a0 \u00a0 \u00a0 \u00a0Dictionary<\/span><<\/span>int<\/span>, int<\/span>><\/span> targetDict<\/span> =<\/span> new<\/span> Dictionary<\/span><<\/span>int<\/span>, int<\/span>><\/span>();<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0for<\/span>(int<\/span> i<\/span> =<\/span> 0<\/span>; i<\/span> <<\/span> nums<\/span>.Length<\/span>; i<\/span>++<\/span>)<\/span>
 \u00a0 \u00a0 \u00a0  {<\/span>
            \/\/\u6c42\u51fa\u7576\u524d\u5143\u7d20\u8207\u76ee\u6a19\u4e4b\u9593\u7684\u5dee\u503c
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0int<\/span> remain<\/span> =<\/span> target<\/span> -<\/span> nums<\/span>[i<\/span>];
<\/span>            \/\/\u5617\u8a66\u5728\u5b57\u5178\u4e2d\u627e\u51fa\u9019\u500b\u5dee\u503c
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(targetDict<\/span>.TryGetValue<\/span>(remain<\/span>, out<\/span> res<\/span>[0<\/span>]))<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  {<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0res<\/span>[1<\/span>] =<\/span> i<\/span>;<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0break<\/span>;<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  }<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\/\/\u627e\u4e0d\u5230\u5c31\u628a\u7576\u524d\u503c\u52a0\u5230\u5b57\u5178\u88e1\uff0c\u8b93\u5f8c\u9762\u7684\u5143\u7d20\u6aa2\u67e5<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(!<\/span>targetDict<\/span>.ContainsKey<\/span>(nums<\/span>[i<\/span>]))<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  {<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0targetDict<\/span>.Add<\/span>(nums<\/span>[i<\/span>], i<\/span>);<\/span>
 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  }<\/span>
 \u00a0 \u00a0 \u00a0  }<\/span> \u00a0 \u00a0  <\/span>
 \u00a0 \u00a0 \u00a0 \u00a0return<\/span> res<\/span>;<\/span>
 \u00a0  }<\/span>
}<\/span><\/pre>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"
\u984c\u76ee\u63cf\u8ff0\uff1a Given an array of integers, return indices of the …<\/p>\n
  [LeetCode\u5237\u984c\u7b46\u8a18] 1 – Two Sum<\/span> Read More »<\/a><\/p>\n","protected":false},"author":1,"featured_media":570,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,16],"tags":[],"class_list":["post-591","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-programming-notes","category-leetcodes"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/lonelinerd.com\/wp-content\/uploads\/2021\/02\/FeatureCover_LeetCoding.png","_links":{"self":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/591","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/comments?post=591"}],"version-history":[{"count":11,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/591\/revisions"}],"predecessor-version":[{"id":603,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/591\/revisions\/603"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/media\/570"}],"wp:attachment":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/media?parent=591"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/categories?post=591"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/tags?post=591"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}