Leetcode No.1 (Two Sum) 心得

ChingYuanYang
Aug 22, 2017 · 3 min read

題目:

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, and you may not use the same element twice.

解答一(也是我一開始的想法):
integers 有正負數,陣列也沒有經過排列,所以直覺就是迴圈跑過陣列所有兩個數相加。
時間複雜度是 O(n​2​​)。
空間複雜度O(1)。

public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == target - nums[i]) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}

解答二:
參考解答,想要加速就是要用 HashMap。在C++有library可以直接套用,這樣不用去處理 Hash Function和資料結構的問題。HashMap的功用是可以很快查詢 key 存不存在,有這題為例子就是可以很快的速度查詢 compliment 存不存在,存在的話就返回 value。

HashMap 查詢速度理論上是 O(1)只要 Hash Function有選好,當然沒選好最差就是 O(n)。以正常情形來說O(1)。
時間複雜度是 O(n)。
空間複雜度是 O(n)。(因為要存 n 個 (key,value),其他一些overhead不因為n大小而增長)。

public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
throw new IllegalArgumentException("No two sum solution");
}

解答三:
一樣是 HashMap,只是稍微改良一下,不是一次先把整個HashMap建好,而是放入一組(key,value)就檢查有沒有compliment。這樣的好處是既然都是要跑遍所有的值,那邊放(key,value)邊檢查就有機會可以不用把整個Hashtable建起來就找到目標了,感覺可以快一點點。

時間複雜度是 O(n)。(同上)
空間複雜度是 O(n)。(同上)

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade