Leetcode No.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, and you may not use the same element twice.
解答一(也是我一開始的想法):
integers 有正負數,陣列也沒有經過排列,所以直覺就是迴圈跑過陣列所有兩個數相加。
時間複雜度是 O(n2)。
空間複雜度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)。(同上)
