This question is part of NeetCode150 series.
Problem 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.
leetcode
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int i=0; i<nums.length; i++){
int diff = target - nums[i];
if(map.containsKey(diff)){
return new int[]{map.get(diff), i};
}else{
map.put(nums[i], i);
}
}
return new int[]{};
}
}
Modified Version of the Problem (Interviewbit)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class Solution {
public int[] twoSum(final int[] A, int B) {
int n = A.length;
Map<Integer, Integer> map = new HashMap<>();
//init with max because we need the least index
int a = Integer.MAX_VALUE;
int b = Integer.MAX_VALUE;
for(int i=0; i<n; i++){
int current = A[i];
//current + secondNumber = B
//=> secondNumber = B - current
if(map.containsKey(B-current)){
int x = map.get(B-current);
int y = i;
//as per the questions, choose the one with min index for second number
if(y < b){
a = x;
b = y;
//if index of second number is equal, then choose the one with least index for the first number
}else if(y == b){
if(x < a){
a = x;
b = y;
}
}
//if current number does not exist in the hash map, only then add it so that we don't update it to the higher index element
}else{
if(!map.containsKey(current)) //this is important because we need to min index for any element
map.put(current, i);
}
}
if(a != Integer.MAX_VALUE){
return new int[]{a+1, b+1};
}
return new int[]{};
}
}