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].
Analysis:
To get two values which the sum of them equals to the target, the brute force one is to have 2 for loop to go over the array twice. This could take O(n^2).
So consider how to get an value very quick, we can have hashtable, which can quickly get the value in nearly O(1).
So basically, what we can do it to put all values in a hash table. Then go over it again to find another value.
Note: here we use the value as key and the index as the value.
Time complexity: O(n)
Space complexity: O(n)
The code is below:
public class Solution {
public int[] twoSum(int[] nums, int target) {
// Hashtable O(n) O(n)
// Corner case
if (nums == null || nums.length == 0) {
return null;
}
HashMap<Integer, Integer> map = new HashMap<>();
// number as key, index as value
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int temp = target - nums[i];
if (map.containsKey(temp) && map.get(temp) != i) {
return new int[] {i, map.get(temp)};
}
}
return null;
}
}
Follow up:
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
Analysis:
Sorted array? Very familiar? Yes, binary search.
Also we can use another powerful method called two pointers: we can have a start and end. If start + end = target, then return them. If start + end < target, we know that start is small, so we add start by 1. Otherwise reduce the end by 1.
Time complexity: O(n)
Space complexity: O(1)
The code is below:
public class Solution {
public int[] twoSum(int[] numbers, int target) {
//Two pointers O(n) O(1)
// Corner case
if (numbers == null || numbers.length == 0) {
return null;
}
int start = 0;
int end = numbers.length - 1;
while (start < end) {
if (numbers[start] + numbers[end] == target) {
return new int[] {start + 1, end + 1};
} else if (numbers[start] + numbers[end] < target) {
start++;
} else {
end--;
}
}
return null;
}
}
Followup:
Design and implement a TwoSum class. It should support the following operations: add and find.
add – Add the number to an internal data structure.
find – Find if there exists any pair of numbers which sum is equal to the value.
For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false
Analysis:
This is more like a design problem. So we can use the similar method to have a hash table to store the value. For adding, we can use map.put() and for finding, we can go through the entrySet and find another value.
Note: for special case where we have multiple values to be the same, like 0, 0, 0 if we want to find 0, it also should return true. So we should add a condition that, if i == j then the occurrence should be larger than 1.
Time complexity: O(n)
Space complexity: O(n)
The code is below:
public class TwoSum {
HashMap<Integer, Integer> map = new HashMap<>();
// Add the number to an internal data structure.
public void add(int number) {
if (map.containsKey(number)) {
map.put(number, map.get(number) + 1);
} else {
map.put(number, 1);
}
}
// Find if there exists any pair of numbers which sum is equal to the value.
public boolean find(int value) {
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
// Find i + j == value
int i = entry.getKey();
int j = value - i;
// special case when i == j
if ((i == j && entry.getValue() > 1) || (i != j && map.containsKey(j))) {
return true;
}
}
return false;
}
}
// Your TwoSum object will be instantiated and called as such:
// TwoSum twoSum = new TwoSum();
// twoSum.add(number);
// twoSum.find(value);
CodeBySteven 