# #6 Three Number Sum

###### tags: `Array` `Medium`

## Problem
Write a function that takes in a non-empty array of distinct integers and an integer representing a target sum. The function should find all triplets in the array that sum up to the target sum and return a two-dimensional array of all these triplets. The numbers in each triplet should be ordered in ascending order, and the triplets themselves should be ordered in ascending order with respect to the numbers they hold.

If no three numbers sum up to the target sum, the function should return an empty array.

### Sample Input

array = [12, 3, 1, 2, -6, 5, -8, 6]
targetSum = 0

### Sample Output

[[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]

<br>

:::spoiler **Optimal Space & Time Complexity**

O(n^2) time | O(n) space - where n is the length of the input array

:::

<br>

:::spoiler Hint 1
Using three for loops to calculate the sums of all possible triplets in the array would generate an algorithm that runs in O(n^3) time, where n is the length of the input array. Can you come up with something faster using only two for loops?
:::

<br>

:::spoiler Hint 2
Try sorting the array and traversing it once. At each number, place a left pointer on the number immediately to the right of your current number and a right pointer on the final number in the array. Check if the current number, the left number, and the right number sum up to the target sum. How can you proceed from there, remembering the fact that you sorted the array?
:::

<br>

:::spoiler Hint 3
Since the array is now sorted (see Hint #2), you know that moving the left pointer mentioned in Hint #2 one place to the right will lead to a greater left number and thus a greater sum. Similarly, you know that moving the right pointer one place to the left will lead to a smaller right number and thus a smaller sum. This means that, depending on the size of each triplet's (current number, left number, right number) sum relative to the target sum, you should either move the left pointer, the right pointer, or both to obtain a potentially valid triplet.
:::

<br/>

<hr/>

## Solutions

### Official

const array = [12, 3, 1, 2, -6, 5, -8, 6];
const targetSum = 0;

// O(n^2) time| 0(n) space 
function threeNumberSum(array, targetSum) { 
  array.sort((a, b) => a - b); 
  const triplets = []; 
  for (let i = 0; i < array.length - 2; i++) {
    let left = i + 1; 
    let right = array.length - 1; 
    while (left < right) {
      const currentSum = array[i] + array[left] + array[right]; 
      if (currentSum === targetSum) { 
        triplets.push([array[i], array[left], array[right]]);
        left++; 
        right--; 
      } else if (currentSum < targetSum) {
        left++; 
      } else if (currentSum > targetSum) {
        right--; 
      }
    }
  }
  return triplets;
}

console.log(threeNumberSum(array, targetSum));

<br>

---

### Everyone's
#### Loop thrice
:::spoiler Raiy

function threeNumSum(array , target){
   const result = [];
   
   for(let i = 0; i < array.length; i++){
     for(let j = i+1; j < array.length; j++){
       for(let r = j+1; r < array.length; r++){
         if(array[i]+array[j]+array[r] === target){
           result.push([array[i],array[j],array[r]])
         }
       }
     } 
   } 
   return result
 }

:::

<br>

#### Loop twice + pointer

:::spoiler 月

// O(n^2) time | ？？？ space
function threeSum(array,targetSum){
  const sortArray = array.sort((a,b) => a-b), len = sortArray.length;
  const answer = [];
  for(let n = 0; n < len; n++){
    let left = n + 1, right = len - 1;
    while(left < right){
      const sum = sortArray[n] + sortArray[left] + sortArray[right];
      if(sum === targetSum){
        answer.push([sortArray[n], sortArray[right], sortArray[left]]);
        left++
      }else if(sum < targetSum){
        left++
      }else{
        right--
      }
    }
  }
  return answer
}

:::

<br>

:::spoiler YC

//time: O(n²) | space:O(n)
function threeSum(targetSum, array){
  const ans=[];
  array.sort((a,b) => a-b);
  for(let i = 0; i < array.length; i++){
    let left = i+1;
    let right = array.length - 1;
    while(left < right){
      const sum = array[i] + array[left] + array[right];
      if(sum === targetSum){
        ans.push([array[i], array[left], array[right]]);
        left++;
        right--;
      }
      else if(sum<targetSum){
        left++;
      }
      else{
        right--;
      }
    }
  }
}

:::

<br>

:::spoiler Becky
- 有做跳過重複

//time: O(n²) | space:O(n)
 function threeSum(nums, target = 0) {     
    let result = [];

    if (nums.length < 3) {
        return result;
    }

    nums.sort((a,b) => a - b);   

    for (let i = 0; i < nums.length - 2 && nums[i] <= target; i++) {

        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        for (var j = i + 1, k = nums.length - 1; j < k;) {            

            let sum = nums[i] + nums[j] + nums[k];
            if (sum < target) {
                j++;
                continue;

            } else if (sum > target) {
                k--;
                continue;
            } 
            result.push([nums[i], nums[j], nums[k]]);
    
            while (nums[j] === nums[j+1]) j++;
            while (nums[k] === nums[k-1]) k--;

            j++;
            k--; 

        }

    }

    return result;
}

:::

<br>

:::spoiler Hao

const getThreeNumberSum = (array, targetSum) => {
  /* time: O(n^2), space: O(n) */
  const getTwoSum = (a, ts) => {
    const sortedArr = a.slice().sort((a, b) => a - b);
    let pointerLeft = 0;
    let pointerRight = a.length - 1;
    let res = [];
    while (pointerRight > pointerLeft) {
      if (sortedArr[pointerLeft] + sortedArr[pointerRight] === ts) res.push([sortedArr[pointerLeft], sortedArr[pointerRight]]);
      if (sortedArr[pointerLeft] + sortedArr[pointerRight] > ts) pointerRight -= 1;
      else pointerLeft += 1;
    }

    return res;
  };
  const sortedArr = array.slice().sort((a, b) => a - b);

  const res = [];
  sortedArr.forEach((el, i) => {
    const targetSumComplements = getTwoSum(sortedArr.slice(i + 1), targetSum - el);
    if (targetSumComplements.length) {
      targetSumComplements.forEach((value) => {
        res.push([el, ...value]);
      });
    };
  });

  return res;
};

:::

<br>

#### Loop twice + hash map
:::spoiler 東

//O(n^2) Time | O(n) Space. n is number of item in array
function threeNumberSum(array, targetSum) {
  array.sort((a, b) => a - b);
  const res = [];
  const numHash = {};
  
  for (let i = 0; i < array.length; i++){
    for (let j = i + 1; j < array.length; j++){
      const restVal = targetSum - array[i] - array[j];
      if(numHash[restVal]) res.push([restVal, array[i], array[j]])
    }
    numHash[array[i]] = true;
  }

  return res.sort((a,b) => a[0] - b[0]);
}

:::

<br>

#### backlog
:::spoiler SOL
暫無

:::

---

## Supplement / Discussion
- 空間複雜度
- Loop twice + hash map: O(2n)
- Loop twice + pointer: O(n)
- 結束條件：`nums.length - 2`