Categories
All 算法

做題筆記: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%的結果。

Leave a Reply

Your email address will not be published. Required fields are marked *