1 Two Sum

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.

Example 1:

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

Example 2:

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

Example 3:

``````Input: nums = [3,3], target = 6
Output: [0,1]
``````

Constraints:

• `2 <= nums.length <= 105`
• `-109 <= nums[i] <= 109`
• `-109 <= target <= 109`
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than `O(n2)` time complexity?

 ``````1 2 3 4 5 6 `````` ``````def twoSum(nums: 'List[int]', target: 'int') -> 'List[int]': map = {} for i, n in enumerate(nums): if n in map: return [map[n], i] map[target-n] = i``````
 `````` 1 2 3 4 5 6 7 8 9 10 `````` ``````func twoSum(nums []int, target int) []int { d := make(map[int]int) for idx, num := range nums { if v, ok := d[num]; ok { return []int{v, idx} } d[target-num] = idx } return nil }``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 `````` ``````public int[] twoSum(int[] nums, int target) { Map map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int comp = target - nums[i]; if (map.containsKey(comp)) { return new int[]{map.get(comp), i}; } map.put(nums[i], i); } return new int[]{}; }``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 `````` ``````class Solution { fun twoSum(nums: IntArray, target: Int): IntArray { val diffMap = mutableMapOf() nums.forEachIndexed { i, num -> diffMap[num]?.let { return intArrayOf(it, i) } diffMap[target - num] = i } return intArrayOf() } }``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 `````` ``````vector twoSum(vector& nums, int target) { unordered_map imap; for (int i = 0;; ++i) { auto it = imap.find(target - nums[i]); if (it != imap.end()) return vector {i, it->second}; imap[nums[i]] = i; } }``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 `````` ``````class Solution { func twoSum(_ nums: [Int], _ target: Int) -> [Int] { var dict = [Int: Int]() for (index, value) in nums.enumerated() { if let i = dict[value] { return [i, index] } else { dict[target - value] = index } } return [] } }``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 `````` ``````pub fn two_sum(nums: Vec, target: i32) -> Vec { use std::collections::HashMap; let mut m: HashMap = HashMap::new(); for (i, v) in nums.iter().enumerate() { match m.get(&(target - *v)) { Some(&i2) => return vec![i as i32, i2], None => m.insert(*v, i as i32), }; } vec![] }``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 `````` ``````/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { let map = {}; for (let i = 0; i < nums.length; i++) { const comp = target - nums[i]; if (map[comp] !== undefined) { return [map[comp], i] } map[nums[i]] = i } return [] };``````