two sum

Question 1:

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) are not zero-based.

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

Input: numbers={2, 7, 11, 15},

target=9

Output: index1=1, index2=2

Answer:

1.排序後，用兩個指針從前後開始查。時間複雜度o(nlgn),結果是over time

快排：

public static void quickSort(int[] sum, int begin, int end) {

　　int left = begin;

　　int right = end;

　　int base = sum[end];

　　while (left < right){

 　　　　while (left < right && sum[left] <= base) {

　　　　　　++left;

　　　　　}

　　　　　sum[right] = sum[left];

　　　　while (left < right && sum[right] >= base) {

　　　　　　　--right;

　　　　}

　　　　sum[left] = sum[right];

　　}

　　sum[left] = base;

　　quickSort(sum, begin, left - 1);

　　quickSort(sum, left + 1, end);

}

2、借助于Hash表，用空間換時間。

hash可以用o(1)的複雜度判斷一個元素是否在hashmap裡。将資料中的資料儲存在hash表中，判斷target-now是否在target中出現過。

code：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

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

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

<code>int</code><code>[] twoSum(</code><code>int</code><code>[] numbers,</code><code>int</code>

<code>target) {</code>

<code>        </code><code>HashMap&lt;Integer, Integer&gt; map =</code><code>new</code>

<code>HashMap&lt;Integer, Integer&gt;();</code>

<code>        </code><code>int</code>

<code>result[] =</code><code>new</code>

<code>int</code><code>[</code><code>2</code><code>];</code>

<code>        </code><code>for</code>

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

<code>            </code><code>int</code>

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

<code>dis = target  - now;</code>

<code>            </code><code>if</code>

<code>(map.containsKey(dis)) {</code>

<code>                </code><code>int</code>

<code>index = map.get(dis) +</code><code>1</code><code>;</code>

<code>                </code><code>result[</code><code>0</code><code>] = index;</code>

<code>                </code><code>result[</code><code>1</code><code>] = i +</code><code>1</code><code>;</code>

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

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

<code>{</code>

<code>                </code><code>map.put(now, i);</code>

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

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

<code>        </code><code>return</code>

<code>result;</code>

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

<code>}</code>

AC