leetCode 1. Two Sum 數組

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

題目大意：

在一個數組中找出2個元素的和等于目标數，輸出這兩個元素的下标。

思路：

最笨的辦法喽，雙循環來處理。時間複雜度O(n*n)。

代碼如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

<code>class</code> <code>Solution {</code>

<code>public</code><code>:</code>

<code>    </code><code>vector&lt;</code><code>int</code><code>&gt; twoSum(vector&lt;</code><code>int</code><code>&gt;&amp; nums, </code><code>int</code> <code>target) {</code>

<code>        </code><code>vector&lt;</code><code>int</code><code>&gt; result;</code>

<code>        </code><code>int</code> <code>i,j;</code>

<code>        </code><code>for</code><code>(i = 0; i &lt; nums.size();i++)</code>

<code>        </code><code>{</code>

<code>            </code><code>for</code><code>(j = i+1; j &lt; nums.size();j++)</code>

<code>            </code><code>{</code>

<code>                </code><code>if</code><code>(nums[i] + nums[j] == target)</code>

<code>                </code><code>{</code>

<code>                    </code><code>result.push_back(i);</code>

<code>                    </code><code>result.push_back(j);</code>

<code>                    </code><code>break</code><code>;</code>

<code>                </code><code>}</code>

<code>            </code><code>}</code>

<code>        </code><code>}</code>

<code>        </code><code>return</code> <code>result;</code>

<code>    </code><code>}</code>

<code>};</code>

采用map的鍵值，把元素做鍵，把元素的下标做值。

21

<code>vector&lt;</code><code>int</code><code>&gt; twoSum(vector&lt;</code><code>int</code><code>&gt; &amp;numbers, </code><code>int</code> <code>target)</code>

<code>{</code>

<code>    </code><code>//Key is the number and value is its index in the vector.</code>

<code>    </code><code>unordered_map&lt;</code><code>int</code><code>, </code><code>int</code><code>&gt; hash;</code>

<code>    </code><code>vector&lt;</code><code>int</code><code>&gt; result;</code>

<code>    </code><code>for</code> <code>(</code><code>int</code> <code>i = 0; i &lt; numbers.size(); i++) {</code>

<code>        </code><code>int</code> <code>numberToFind = target - numbers[i];</code>

<code>            </code><code>//if numberToFind is found in map, return them</code>

<code>        </code><code>if</code> <code>(hash.find(numberToFind) != hash.end()) {</code>

<code>            </code> 

<code>            </code><code>result.push_back(hash[numberToFind]);</code>

<code>            </code><code>result.push_back(i);            </code>

<code>            </code><code>return</code> <code>result;</code>

<code>            </code><code>//number was not found. Put it in the map.</code>

<code>        </code><code>hash[numbers[i]] = i;</code>

<code>    </code><code>return</code> <code>result;</code>

<code>}</code>

<code></code>

本文轉自313119992 51CTO部落格，原文連結:http://blog.51cto.com/qiaopeng688/1836898