做題筆記：Two Sum (Java)
驚恐自己要找不到工作了，開始做題，記錄一下做題筆記。第一道，是刷題界的 Hello World —— Two Sum。
題目描述：
給定一個整數數組 nums 和一個整數 target，返回兩個數字的索引，使它們相加為 target。
假設每個輸入都只有一個解決方案，並且不會使用相同的元素兩次。
可以按任何順序返回答案。
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]Foreach 暴力解法：
第一次刷題，算法小白，只想得到這種方式：
class Solution {
public int[] twoSum(int[] nums, int target) {
int [] empty = new int[2];
int len = nums.length;
for(int i = 0; i < len; i++){
for(int j = 0; j < len; j++){
if (nums[i]+nums[j] == target&& i != j){
empty[0] = i;
empty[1] = j;
return empty;
}
}
}
return null;
}
}果不其然，106 ms，超過了10%的答案，好歹是通過了對吧……
以前上課做作業時，都是秉持著能跑就行的態度，習慣很差，現在我開始認真考慮優化的問題了，也算是一大進步。
Hashmap 解法：
看了 discussion 之後，追求高效率，這道題是應該使用 Hashmap 的：
class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(target - numbers[i])) {
result[1] = i;
result[0] = map.get(target - numbers[i]);
return result;
}
map.put(numbers[i], i);
}
return result;
}
}3 ms，超過85%的結果。