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⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• 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²)
• Hash
  depends on Hash's mehtod,containsKey() or get(),
  =>O(n)

Conclusion

學習java Map類用法.

tags: Leetcode Easy Array