One would resolve the two sum problem by using two pointers or a hash table algorithm

• If the input array is sorted or the output does not require returning array indices, one would use both two-pointers and hash table algorithm

• If the input array is not sorted and the output requires returning array indices, one would use the hash table algorithm

Two pointers algorithm uses two indices and walks inward from both ends to reduce the iteration time when searching elements in a sorted linear collection

Hash table has a better performance than other collections in terms of looking up elements

## Two Sum problem 1

Given an array of integers `a[n]` and an integer number `k` as a target sum. Determine whether there is a pair of elements `a[i]` and `a[j]` that sums exactly to `k`

Example

• Given an array a [1, 3, 7] and k = 8 then the answer is `true`, but given k=5 then the answer is `false`

• Given an array a [4, -9, 0, 11, 6, -20, 1, 7] and k = -14 then the answer is `true`, but given k = -15 then the answer is `false`

### Approach: Brute force

• Use 2 for-loop to try all pairs in the given array `a` to see if any of them add up to `k`
``````import java.util.Arrays;

public class TwoSum_BruteForce {
static boolean bruteForce(int[] a, int k) {
for (int i = 0; i < a.length ; i++) {
for (int j = i+1; j < a.length; j++) {
if (a[i] + a[j] == k) return true;
}
}

return false;
}

public static void main(String[] args) {
int[] a = {1, 3, 7};
System.out.println(bruteForce(a, 8));
System.out.println(bruteForce(a, 5));

int[] b = {4, -9, 0, 11, 6, -20, 1, 7};
System.out.println(bruteForce(b, -14));
System.out.println(bruteForce(b, -15));
}
}
``````
• Output
``````true
false
true
false
``````
• Time complexity: O(n2) as with each element, the algorithm loops through the array which takes O(n) time

• Space complexity: O(1)

### Approach: Two pointers

• Sort the given array

• Walk two indices `i` and `j` inward from both ends of the array. While `i` is still less than `j`, calculate the sum `s` of their corresponding elements. If `s` equals to the given `k` then return `true` and exit the algorithm immediately. If `s` is less than `k`, increases `i` by 1, otherwise decreases `j` by 1

• Finally, return `false` as no pair has a sum equal to `k`

``````import java.util.Arrays;

public class TwoSum_TwoPointers {
static boolean twoPointers(int[] a, int k) {
Arrays.sort(a);

int i = 0;
int j = a.length - 1;

while (i < j) {
int sum = a[i] + a[j];

if (sum == k) {
return true;
} else if (sum < k) {
i++;
} else {
j--;
}
}

return false;
}

public static void main(String[] args) {
int[] a = {1, 3, 7};
System.out.println(twoPointers(a, 8));
System.out.println(twoPointers(a, 5));

int[] b = {4, -9, 0, 11, 6, -20, 1, 7};
System.out.println(twoPointers(b, -14));
System.out.println(twoPointers(b, -15));
}
}
``````
• Output
``````true
false
true
false
``````
• Time complexity: O(nlogn) due to the cost of sorting

• Space complexity: O(1)

### Approach: Hash table

• Create a new HashSet `h`

• Loop through the given array `a` . For each array element `a[i]`, check if existing an element `a[j]` that `a[j] = k - a[i]`. If yes return `true` and exit the algorithm immediately, otherwise add `a[i]` into `h`

• Finally, return `false` as no pair has a sum equal to `k`

``````import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class TwoSum_HashTable {
static boolean hashTable(int[] a, int k) {
HashSet<Integer> h = new HashSet<>();
for (int i = 0; i < a.length ; i++) {
if (h.contains(k - a[i])) return true;
}

return false;
}

public static void main(String[] args) {
int[] a = {1, 3, 7};
System.out.println(hashTable(a, 8));
System.out.println(hashTable(a, 5));

int[] b = {4, -9, 0, 11, 6, -20, 1, 7};
System.out.println(hashTable(b, -14));
System.out.println(hashTable(b, -15));
}
}
``````
• Output
``````true
false
true
false
``````
• Time complexity: O(n) as with each element, the algorithm looks up in the hash table which takes O(1) time

• Space complexity: O(n) as the algorithm use a hash table size `n`

## Two Sum problem 2

Given an array of integers `nums` and an integer number `k` as a target sum. Return indices of the two numbers such that they add up to `k`

Example

• Input: nums = [1, 3, 7], k = 8. Output: [0, 2]

• Input: nums = [4, -9, 0, 11, 6, -20, 1, 7], k = -14. Output: [4, 5]

### Approach: HashTable

Loops through the array `nums` and puts each element value `nums[i]` and index `i` into a HashMap as key and value

Each time, check if the map contains key `k - nums[i]` then return `{map.get(k - nums[i]), i}` as the result

``````public int[] twoSum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int i=0; i<nums.length; i++) {
if (map.containsKey(k - nums[i])) {
return new int[]{map.get(k - nums[i]), i};
}
map.put(nums[i], i);
}

return null;
}
``````

Time complexity: O(n)
Space complexity: O(n)