[LeetCode] 1. Two Sum

轉自LeetCode

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

<Solution>

這題不難，因為題目有說每個input只會有一個答案

所以對於每個數字 n，要找的配對就是 target - n

那這邊使用 unordered_map 來存 {value : index} 這個配對

是因為 unordered_map 是用 hash table 實做，所以它的存取速度很快，可以視作O(1)

解法概念如下

• 算出要找的配對數字

• 看看是否已經在 unordered_map 裡了。有就回傳答案，沒有就塞到 unordered_map

code如下

C++

	class Solution {
	public:
	vector<int> twoSum(vector<int>& nums, int target) {
	vector<int> ans(2,-1); //> fixed length of 2
	unordered_map<int, int> table; //> hashmap
	int complement;
	for(auto i = 0; i < nums.size(); ++i) {
	complement = target - nums[i];
	//> if the complement is already in unordered_map
	//> return the ans
	if(table.find(complement) != table.end()) {
	ans[0] = table[complement]; //> complement was inserted before i
	ans[1] = i;
	return ans;
	}
	//> insert to unordered_map
	//> key : element's value, value : index
	table[nums[i]] = i;
	}
	//> actually this line will never be executed
	return ans;
	}
	};

view raw twosum.cpp hosted with ❤ by GitHub

Java

	public class Solution {
	public int[] twoSum(int[] nums, int target) {
	int[] ans = new int[2];
	HashMap<Integer, Integer> lookupMap = new HashMap<>();
	int complement;
	for(int i = 0; i < nums.length; i++) {
	complement = target - nums[i];
	//>> find complement in the HashMap
	if(lookupMap.containsKey(complement)) {
	ans[0] = lookupMap.get(complement);
	ans[1] = i;
	break;
	}
	//>> key: nums[i], value : index
	lookupMap.put(nums[i], i);
	}
	return ans;
	}
	}

view raw twoSum.java hosted with ❤ by GitHub

Kotlin

	class Solution {
	fun twoSum(nums: IntArray, target: Int): IntArray {
	val map = mutableMapOf<Int,Int>()
	for(i in nums.indices) {
	if(map[target-nums[i]] != null) {
	return intArrayOf(map[target-nums[i]]!!, i)
	}
	map[nums[i]] = i
	}
	return intArrayOf(0, 0)
	}
	}

view raw two_sum.kt hosted with ❤ by GitHub