# LeetCode 1. Two Sum (Java)
###### tags: `leetcode` `Java`

## Description
> 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.

>給一個整數數組，找到兩個數使得他們的和等於一個給定的數 target。 你需要實現的函數twoSum需要返回這兩個數的下標, 並且第一個下標小於第二個下標。注意這裡下標的範圍是 0 到 n-1

## Example

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2]

## Idea
+ Approach 1 (暴力法)
- 利用雙迴圈找出哪兩個數字可以符合``target``，時間複雜度偏高$O(n^2)$
+ Approach 2 (HashMap)
- 遍歷整個陣列，將``target``和當前數字相減並存在HashMap裏並在接下來的迴圈當中檢查當前數字在HashMap中是否有相同數字
- 例：``map.get(nums[i])!=null``代表HashMap中有我要的數字
- 整體時間複雜度降到$O(n)$
## Code
### Approach 1

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

### Approach 2

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int len = nums.length;
        int[] result = new int[2];
        for (int i = 0;i < len;i++){
            if(map.get(nums[i]) != null){//檢查HashMap中是否有此數
                return new int[] {map.get(nums[i]), i};
            }
            map.put(target - nums[i],i);//將理想配對數字放到HashMap中
        }
        return result;
    }
}

方法二相較於方法一暴力解法整整快出了50倍
## Result
### Approach 1
Runtime: **48** ms, faster than **28.98**% of Java online submissions for Two Sum.
Memory Usage: **39.4** MB, less than **37.92**% of Java online submissions for Two Sum.
### Approach 2
Runtime: **1** ms, faster than **99.59**% of Java online submissions for Two Sum.
Memory Usage: **39.2** MB, less than **50.00**% of Java online submissions for Two Sum.