Given an array of integers, 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 you returned
answers (both index1 and index2) are not zero-based.

For example:

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Two Sum using HashMap in Java

public class Solution {
public int[] twoSum(int[] numbers, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int[] result = new int[2];
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(numbers[i])) {
int index = map.get(numbers[i]);
result[0] = index+1 ;
result[1] = i+1;
break;
} else {
map.put(target - numbers[i], i);
}
}
return result;
}
}

Time complexity depends on the put and gets operations of HashMap which is normally O(1). The time complexity of this solution: O(n).

Two Sum using a sorted array

This problem is similar to Two Sum. To solve this problem, we can use two points to scan the array from both sides. See
Java solution below:

public int[] twoSum(int[] numbers, int target) {
if (numbers == null || numbers.length == 0)
return null;
int i = 0;
int j = numbers.length - 1;
while (i < j) {
int x = numbers[i] + numbers[j];
if (x < target) {
++i;
} else if (x > target) {
j--;
} else {
return new int[] { i + 1, j + 1 };
}
}
return null;
}

Two Sum using Data structure design

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 whose sum is equal to the value.
For example,
add(1);
add(3);
add(5);
find(4) -> true
find(7) -> false

Since the desired class need add and get operations, HashMap is a good option for
this purpose.

public class TwoSum {
private HashMap<Integer, Integer> elements = new HashMap<Integer,
Integer>();
public void add(int number) {
if (elements.containsKey(number)) {
elements.put(number, elements.get(number) + 1);
} else {
elements.put(number, 1);
}
}
public boolean find(int value) {
for (Integer i : elements.keySet()) {
int target = value - i;
if (elements.containsKey(target)) {
if (i == target && elements.get(target) < 2) {
continue;
}
return true;
}
}
return false;
}
}

Solve Three Sum problem in Java

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets.

For example,

given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)

A better solution is using two pointers instead of one. This makes the time complexity of O(n2ˆ).
To avoid duplicate, we can take advantage of sorted arrays, i.e., move pointers by >1 to use the same element only once.

public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (num.length < 3)
return result;
// sort array
Arrays.sort(num);
for (int i = 0; i < num.length - 2; i++) {
// //avoid duplicate solutions
if (i == 0 || num[i] > num[i - 1]) {
int negate = -num[i];
int start = i + 1;
int end = num.length - 1;
while (start < end) {
//case 1
if (num[start] + num[end] == negate) {
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(num[i]);
temp.add(num[start]);
temp.add(num[end]);
result.add(temp);
start++;
end--;
//avoid duplicate solutions
while (start < end && num[end] == num[end + 1])
end--;
while (start < end && num[start] == num[start - 1])
start++;
//case 2
} else if (num[start] + num[end] < negate) {
start++;
//case 3
} else {
end--;
}
}
}
}
return result;
}

Solve Four Sum problem in Java

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c+ d = target? Find all unique quadruplets in the array which gives the sum of the target.

Note: Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤b ≤ c ≤ d) The solution set must not contain duplicate quadruplets.

For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)

public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
Arrays.sort(num);
HashSet<ArrayList<Integer>> hashSet = new HashSet<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < num.length; i++) {
for (int j = i + 1; j < num.length; j++) {
int k = j + 1;
int l = num.length - 1;
while (k < l) {
int sum = num[i] + num[j] + num[k] + num[l];
if (sum > target) {
l--;
} else if (sum < target) {
k++;
} else if (sum == target) {
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(num[i]);
temp.add(num[j]);
temp.add(num[k]);
temp.add(num[l]);
if (!hashSet.contains(temp)) {
hashSet.add(temp);
result.add(temp);
}
k++;
l--;
}
}
}
}
return result;
}

Here is the hashCode method of ArrayList. It makes sure that if all elements of the two lists are the same, then the hash code of the two lists will be the same. Since each element in the ArrayList is Integer, the same integer has the same hash code.
int hashCode = 1;
Iterator<E> i = list.iterator();
while (i.hasNext()) {
E obj = i.next();
hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
}

Solve Three Sum Closest problem in Java

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution. For example, given array S = -1 2 1 -4, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2)

This problem is similar with 2 Sum. This kind of problem can be solved by using a similar approach, i.e., two pointers from both left and right.

public class Solution {
public int threeSumClosest(int[] num, int target) {
int min = Integer.MAX_VALUE;
int result = 0;
Arrays.sort(num);
for (int i = 0; i < num.length; i++) {
int j = i + 1;
int k = num.length - 1;
while (j < k) {
int sum = num[i] + num[j] + num[k];
int diff = Math.abs(sum - target);
if(diff == 0) return 0;
if (diff < min) {
min = diff;
result = sum;
}
if (sum <= target) {
j++;
} else {
k--;
}
}
}
return result;
}
}

Time Complexity is O(n2ˆ).