Leetcode --- Two Sum (Easy)
===

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

### Constrains:

* 2 <= nums.length <= 10^4^
* -10^9^ <= nums[i] <= 10^9^
* -10^9^ <= target <= 10^9^
* Only one valid answer exists.

### Example

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

## Solutions:
* ### Method 1 : Brute Force solve (in C)

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 
int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{
    *returnSize = 2;
    for(int i =0;i< numsSize;i++)
    {
        for(int j=i+1;j<numsSize;j++)
        {
            if(nums[i] + nums[j]  == target)
            {
                int* res = (int*) malloc(2*sizeof(int));
                res[0]=i;
                res[1]=j;
                return res;
            }   
        }
    }
    return NULL;
}

### Submissions on Leetcode

Runtime: **84 ms**, faster than 5.44% of C online submissions for Two Sum.
Memory Usage: **6.6 MB**, less than 6.64% of C online submissions for Two Sum.

* ### Method 2 : Hash solve(in java)

import java.util.*;
class Solution {
    public int[] twoSum(int[] nums, int target) 
    {
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        int k =0;
        for(int tmp : nums)
        {
            map.put(tmp,k);
            k++;
        }
        for(int i=0;i<nums.length;i++)
        {
            int duel = target - nums[i];
            if( map.containsKey(duel) && map.get(duel) != i)
            {
                return new int[]{i,map.get(target -nums[i])};
            }            
        }
        return new int[]{0};
    }
}

### Submissions on Leetcode

Runtime: **3 ms**, faster than 61.45% of Java online submissions for Two Sum.
Memory Usage: **40.4 MB**, less than 13.43% of Java online submissions for Two Sum.

### *Note:* Map 類別分支:
* Map(**interface**)
* ==inheritance==
* SortMap(**interface**)
* NavigableMap(**interface**)
* ConcuuentMap(**interface**)
* ==implements==
* HashMap(**class**)
* TreeMap(**class**)
* WeakHashMap(**class**)
* EnumMap(**class**)
* LinkedHashMap(**class**)

## Complexity Analysis

* Brute Force
=>==O(n^2^)==
* Hash
depends on Hash's mehtod,containsKey() or get(),
=>==O(n)==

## Conclusion

學習java Map類用法.

###### tags: `Leetcode` `Easy` `Array`