## 15. 3Sum

https://leetcode.com/problems/3sum/description/

<br>

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

- Time complexity: O(n^2)
- Space complexity: O(1)

:::

<br>

<hr/>

## Solutions

:::spoiler 東

:::

<br>

:::spoiler Hao

function threeSum(nums) {
  const results = [];

  if (nums.length < 3) return results;

  // having the numbers in ascending order will make this problem much easier.
  // also, knowing the overall problem  will take at least O(N^2) time, we can
  // afford the O(NlogN) sort operation
  nums = nums.sort((a, b) => a - b);

  let target = 0;

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

    let j = i + 1;
    let k = nums.length - 1;

    while (j < k) {
      let sum = nums[i] + nums[j] + nums[k];

      if (sum === target) {
        results.push([nums[i], nums[j], nums[k]]);

        while (nums[j] === nums[j + 1]) j++;
        while (nums[k] === nums[k - 1]) k--;

        j++;
        k--;
      }
      else if (sum < target) j++;
      else k--;
    }
  }

  return results;
}

:::

<br>

:::spoiler YC

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    if(nums.length < 3) return []; //early return
    nums.sort((a,b) => a-b);
    const ans = []
    for(let i = 0; i < nums.length; i++){
        let left = i + 1;
        let right = nums.length - 1;
        if(nums[i] > 0) return ans; //early return because the array is sorted
        if(nums[i] === nums[i-1]) continue;
        while(left < right){
            const sum = nums[i] + nums[left] + nums[right];
            if(sum < 0) left++;
            else if(sum > 0) right--;
            else{
                ans.push([nums[i], nums[left], nums[right]]);
                left++;
                right--;
                while(nums[left] === nums[left-1]) left++;
                while(nums[right] === nums[right+1]) right--;
            }
        }
    }
    return ans;
};

:::

<br>

:::spoiler SOL

:::

---

## Supplement / Discussion

### 東

### Hao

[JavaScript with lots of explanatory comments!](https://leetcode.com/problems/3sum/solutions/281302/javascript-with-lots-of-explanatory-comments/)

"Three" pointers: employ indexs `i`, `j`, `k` to indicate the number. Iterate `i` with the following steps:

1. Fix `i` first, and so we have only two pointers `j`, `k` left.
2. Sum up `i`, `j`, `k` to see if reach `targetSum` while move `j` and `k` closer to each other
3. Add early break/continue during iterations
- When `nums[i] > targetSum`
- When `nums[i] === nums[i - 1]`
- When `nums[j] === nums[j - 1]`
- When `nums[k] === nums[k - 1]`

### YC
1. sort the array
2. set three variables: `i`, `left`, `right`
- `i` is a for-loop variable
- `left` and `right` serve as left-right pointer
4. remove duplicate triplets
- `nums[i] === nums[i-1]`
- `nums[left] === nums[left-1]`
- `nums[right] === nums[right+1]`
5. (nice to have) early return
- `nums.length < 3`
- `nums[i] > 0`: because the array is sorted

### SOL

#### 3 loops 👎🏻👎🏻👎🏻
> [-1,0,1,2,-1,-4]

1. Sort the input array in ascending order

> [-4,-1,-1,0,1,2,]

2. Loop through each value in the array.
3. Calculate the target value needed for two additional elements to sum up to zero.
4. Iterate through each value in sub-array1 (remaining elements after current value).

> -4, [-1,-1,0,1,2,] find a + b = 4

5. Calculate the value needed for the third element to complete the triplet sum.
6. Iterate through each value in sub-array2 (remaining elements after current value).
7. Search for the value in the sub-array2 that matches the calculated target value.
8. Add the triplet [a, b, c] to the result array if found.
> -1, [,-1,0,1,2,] find 1
> ....

var threeSum = function(nums) {
    const result = []
    nums.sort((a,b)=>a-b)
    let preNum1;
    nums.forEach((a, index)=>{
        if( preNum1 !== a ){
            const target = 0 - a;
            const rest = nums.slice(index+1)
            let preNum2;
            rest.forEach((b, index)=>{
                if(preNum2 !== b){
                    const target2 = target - b;
                    const rest2 = rest.slice(index+1)
                    const find = rest2.find((c)=> c === target2)
                    if(find || find === 0){
                        result.push([a, b,find])
                    };
                }
                preNum2 = b
            })
        }
        preNum1 = a 
    });
    return result;
};

#### two poniters 👍👍👍

1. Sort the input array in ascending order.
2. Loop through the array, excluding the last two elements.
3. Skip duplicates.
4. Use a two-pointers approach (left-right pointers) that move toward each other.
5. Calculate the sum
- If the sum === target:
a. Add the triplet to the result array.
b. ==Eliminate duplicate pointers by moving them.==
c. Move both pointers.
- If sum < target, move leftPointer.
- If sum > target, move rightPointer.

var threeSum = function(nums) {
    const result = []
    const target = 0;
    nums.sort((a,b)=>a-b)
    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let leftPointer = i+1;
        let rightPointer = nums.length -1;
        while( leftPointer < rightPointer ){
            const sum = nums[i] + nums[leftPointer] + nums[rightPointer]
            if(sum === target){
                result.push([nums[i], nums[leftPointer], nums[rightPointer] ])
                while(nums[leftPointer + 1] === nums[leftPointer]) leftPointer++;
                while(nums[rightPointer - 1] === nums[rightPointer]) rightPointer--;
                leftPointer++;
                rightPointer--;
            } else if(sum<target){
                leftPointer++;
            } else {
                rightPointer--;
            }
        }
    }
    return result;
};

---
#### Supplement (psuedo code from YC)

/*
 * 3 variables: i, j, k for-loop 3 times: O(n^3)
 * j, k -> left, right: O(n^2)
 * remove duplicate triplet: i, left, right
 * */

var threeSum = function(nums) {
    // sort
    const ans = []
    for(let i = 0, ...){
        if(nums[i]>0) return ans;
        let left = i+1;
        let right = nums.length - 1;
        while(left < right){
            const sum = ...
            if(sum < 0) left++
            else if (sum > 0) right--;
            else{
                ans.push([i,left,right])
                left++;
                right--;
                while(left === left-1) left++;
                while(right === right+1) right--;
            }
        }
    }
    return ans;
    
}