# #1 Two Number Sum

###### tags: `Array` `Easy`

## Problem
Write a function that takes in a non-empty array of distinct integers and an integer representing a target sum. If any two numbers in the input array sum up to the target sum, the function should return them in an array, in any order. If no two numbers sum up to the target sum, the function should return an empty array.

Note that the target sum has to be obtained by summing two different integers in the array; you can't add a single integer to itself in order to obtain the target sum.

You can assume that there will be at most one pair of numbers summing up to the target sum.

### Sample Input

array = [3, 5, -4, 8, 11, 1, -1, 6]
targetSum = 10

### Sample Output

[-1, 11]

<br/>

<hr/>

## Solutions
### Use two for loops

// O(n^2) time | O(1) space
function twoNumberSum(array, targetSum) {
  for (let i = 0; i < array.length - 1; i++){
      const firstNum = array[i];
      for (let j = i + 1; j < array.length; j++){
          const secondNum = array[j];
          if (firstNum + secondNum === targetSum){
                return [firstNum, secondNum];
          }
      }
  }
  return []
}

### Hash Map

// O(n) time | O(n) space
function twoNumberSum(array, targetSum){
    const nums = {};
    for (const num of array){
        const potentialMatch = targetSum - num;
        if (potentialMatch in nums){
            return [potentialMatch, num];
        }else{
            nums[num] = true;
        }
    }
    return [];
}

### Two Pointer

// O(nlog(n)) | O(1) space
function twoNumberSum(array, targetSum){
    array.sort((a, b) => a - b);
    let left = 0;
    let right = array.length - 1;
    while (left < right){
        const currentSum = array[left] + array[right];
        if (currentSum === targetSum){
            return [array[left], array[right]];
        }else if (currentSum < targetSum){
            left++;
        }else if(currentSum > targetSum){
            right--;
        }
    }
    return []
}

---
## Additional information
### 關於 Array 的補充介紹
#### 一般高階語言的陣列
- 由相同類型的元素所組成
- 由一塊連續的記憶體位置儲存(通常宣告後的長度是不能改變的)

#### JS 陣列
- 可以存放不同型別的元素（->動態型別）
- 陣列本質上屬於一種特殊的物件

typeof [] // "object"

### 操作 JS 陣列

|Function | Runtime | Description |
| -------- | -------- | -------- |
|array.push | O(1) | Insert element to the end of the array|
|array.pop | O(1) | Remove element to the end of the array|
|array.shift | O(n) | Remove element to the beginning of the array|
|array.unshift | O(n) | Insert element(s) to the beginning of the array|
|array.slice | O(n) | Returns a copy of the array from beginning to end.|
|array.splice | O(n) | Changes (add/remove) the array|

### map()
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map