LeetCode Note Java 00001：Two Sum

輸入一個 intArray nums 與一個 int target，回傳一個 intArray，內容為 nums 中相加為 target 的兩個 int 的索引。

題目

Two Sum Easy

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have *exactly* one solution, and you may not use the same element twice.

You can return the answer in any order.

我的解法

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            int diff = target - nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == diff) {
                    return new int[] {i, j};
                }
            }
        }
        return new int[2];
    }
}

雙層迴圈，時間複雜度：O(n*n)

檢討

看其他人滿多都在減少時間複雜度，我功力還不夠，所以等我看得夠多再來嘗試。

My (short) Java solution [O(n) + HashMap!]

重新嘗試：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> diffMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            int diff = target - nums[i];
            if (diffMap.containsKey(nums[i])) {
                return new int[] {diffMap.get(nums[i]), i};
            }
            diffMap.put(diff, i);
        }
        return new int[2];
    }
}

已經知道雙層迴圈太 low 了，所以趕緊換成單迴圈跟查字典方式，時間複雜度：O(n)。

重點物件或方法：

• HashMap