Array
Hash Table
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.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: 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 <= 104
-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?
Solutions
Solution 1: Hash Table
We can use the hash table $m$ to store the array value and the corresponding subscript.
Traverse the array nums
, when you find target - nums[i]
in the hash table, it means that the target value is found, and the index of target - nums[i]
and $i$ are returned.
The time complexity is $O(n)$ and the space complexity is $O(n)$. Where $n$ is the length of the array nums
.
Python3 Java C++ Go TypeScript Rust JavaScript C# PHP Scala Swift Ruby Nim
class Solution :
def twoSum ( self , nums : List [ int ], target : int ) -> List [ int ]:
m = {}
for i , x in enumerate ( nums ):
y = target - x
if y in m :
return [ m [ y ], i ]
m [ x ] = i
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution {
public int [] twoSum ( int [] nums , int target ) {
Map < Integer , Integer > m = new HashMap <> ();
for ( int i = 0 ;; ++ i ) {
int x = nums [ i ] ;
int y = target - x ;
if ( m . containsKey ( y )) {
return new int [] { m . get ( y ), i };
}
m . put ( x , i );
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution {
public :
vector < int > twoSum ( vector < int >& nums , int target ) {
unordered_map < int , int > m ;
for ( int i = 0 ;; ++ i ) {
int x = nums [ i ];
int y = target - x ;
if ( m . count ( y )) {
return { m [ y ], i };
}
m [ x ] = i ;
}
}
};
func twoSum ( nums [] int , target int ) [] int {
m := map [ int ] int {}
for i := 0 ; ; i ++ {
x := nums [ i ]
y := target - x
if j , ok := m [ y ]; ok {
return [] int { j , i }
}
m [ x ] = i
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 function twoSum ( nums : number [], target : number ) : number [] {
const m : Map < number , number > = new Map ();
for ( let i = 0 ; ; ++ i ) {
const x = nums [ i ];
const y = target - x ;
if ( m . has ( y )) {
return [ m . get ( y ) ! , i ];
}
m . set ( x , i );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 use std :: collections :: HashMap ;
impl Solution {
pub fn two_sum ( nums : Vec < i32 > , target : i32 ) -> Vec < i32 > {
let mut m = HashMap :: new ();
for ( i , & x ) in nums . iter (). enumerate () {
let y = target - x ;
if let Some ( & j ) = m . get ( & y ) {
return vec! [ j as i32 , i as i32 ];
}
m . insert ( x , i as i32 );
}
unreachable! ()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 /**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function ( nums , target ) {
const m = new Map ();
for ( let i = 0 ; ; ++ i ) {
const x = nums [ i ];
const y = target - x ;
if ( m . has ( y )) {
return [ m . get ( y ), i ];
}
m . set ( x , i );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 public class Solution {
public int [] TwoSum ( int [] nums , int target ) {
var m = new Dictionary < int , int > ();
for ( int i = 0 , j ; ; ++ i ) {
int x = nums [ i ];
int y = target - x ;
if ( m . TryGetValue ( y , out j )) {
return new [] { j , i };
}
if ( ! m . ContainsKey ( x )) {
m . Add ( x , i );
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[]
*/
function twoSum($nums, $target) {
$m = [];
foreach ($nums as $i => $x) {
$y = $target - $x;
if (isset($m[$y])) {
return [$m[$y], $i];
}
$m[$x] = $i;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 import scala . collection . mutable
object Solution {
def twoSum ( nums : Array [ Int ], target : Int ): Array [ Int ] = {
var map = new mutable . HashMap [ Int , Int ]()
for ( i <- 0 to nums . length ) {
if ( map . contains ( target - nums ( i ))) {
return Array ( map ( target - nums ( i )), i )
} else {
map += ( nums ( i ) -> i )
}
}
Array ( 0 , 0 )
}
}
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 m = [ Int : Int ]()
var i = 0
while true {
let x = nums [ i ]
let y = target - nums [ i ]
if let j = m [ target - nums [ i ]] {
return [ j , i ]
}
m [ nums [ i ]] = i
i += 1
}
}
}
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum ( nums , target )
nums . each_with_index do | x , idx |
if nums . include? target - x
return [ idx , nums . index ( target - x ) ] if nums . index ( target - x ) != idx
end
next
end
end
1
2
3
4
5
6
7
8
9
10
11
12 import std / enumerate
proc twoSum ( nums : seq [ int ] , target : int ): seq [ int ] =
var
bal : int
tdx : int
for idx , val in enumerate ( nums ):
bal = target - val
if bal in nums :
tdx = nums . find ( bal )
if idx != tdx :
return @[ idx , tdx ]