two number sum

Refer to : https://www.algoexpert.io/questions/Two%20Number%20Sum

Two number sum

1. problem statement.

给定一个不含重复数字的数组和一个目标值，返回一个长度为2的数组，这个数组包含的两个数的和要等于目标值，原数组里面的值不能重复使用，如果没有这样的两个值使得它们的和等于目标值，返回空数组。

2. brute force（O(n^2), O(1)）

1 def twoNumberSum(array, targetSum):
2     for i in range(len(array)-1):
3         for j in range(i+1, len(array)):
4             if array[i] + array[j] == targetSum:
5                 return[array[i], array[j]]
6     return[]

 1 class Program {
 2   public static int[] twoNumberSum(int[] array, int targetSum) {
 3     
 4         for(int i = 0; i < array.length-1; i++){
 5             for(int j = i+1; j < array.length; j++){
 6                 if(array[i] + array[j] == targetSum){
 7                     return new int[] {array[i], array[j]};
 8                 }
 9             }
10         }
11     return new int[0];
12   }
13 }

3. hash map(O(n), O(n))

1 def twoNumberSum(array, targetSum):
2     nums = {}
3     for num in array:
4         b = targetSum - num
5         if b in nums:
6             return[b, num]
7         else:
8             nums[num] = True //mark the num as true.
9     return[]

 1 class Program {
 2   public static int[] twoNumberSum(int[] array, int targetSum) {
 3     HashSet<Integer> set = new HashSet<>();
 4         for(int i: array){
 5             int j = targetSum - i;
 6             if(set.contains(j)){
 7                 return new int[] {i,j};
 8             }else{
 9                 set.add(i);
10             }
11         }
12     return new int[0];
13   }
14 }

4. Sort && Pointers(O(nlogn), O(1))

 1 def twoNumberSum(array, targetSum):
 2     array.sort()
 3     left = 0
 4     right = len(array)-1
 5     while left<right:
 6         if array[left] + array[right] == targetSum:
 7             return [array[left], array[right]]
 8         elif array[left] + array[right] > targetSum:
 9             right -= 1
10         elif array[left] + array[right] < targetSum:
11             left += 1
12     return[]

 1 class Program {
 2   public static int[] twoNumberSum(int[] array, int targetSum) {
 3     Arrays.sort(array);
 4         int left = 0, right = array.length-1;
 5         while(left < right){
 6             int currSum = array[left] + array[right];
 7             if(currSum == targetSum){
 8                 return new int[] {array[left], array[right]};
 9             }else if(currSum > targetSum){
10                 right--;
11             }else if(currSum < targetSum){
12                 left++;
13             }
14         }
15     return new int[0];
16   }
17 }