iT邦幫忙

2021 iThome 鐵人賽

DAY 6
1
Software Development

30天用JavaScript刷題刷起來!系列 第 6

Day 06:3 Sum

在Two Sum 中 我們一開始最初的想法是用2次的loop檢查,那換做這3 Sum我們當然可以用三次loop來解,
時間複雜度直接飆升到O(n^3)。

還記得我們昨天最後一個方式嗎?
其實就是利用昨天用到的左右指針的方式。

舉一個Input Array: [12, 3, 1, 2, -6, 5, 0, -8, -1]
Target Sum: 0

如果以這題為例子,先把要檢查的陣列設定為
1.不是空陣列
2.陣列中每數都不同
來思考這題題目。

step1: 我們一樣先將陣列排序
step2: 從陣列的第一個數為主,依序找剩下的數中,可以照到兩個數和第一個數相加,最後達到目標總和

以下面例子來說

https://ithelp.ithome.com.tw/upload/images/20210921/20141729DLhHRNGJbz.jpg

當我們把排序後的陣列開始檢查(也就是這裡的-8)
我們先把第一個數 -8 當作基準,往後(-6)開始尋找,開始找出兩個數,可以符合加上-8可以變成目標總和(0)

我們把左指標放在第一個基準數右邊,右指標一樣放在最後面。
以第一次來說,
我們可以得到 sum = -8 + -6 + 12 = -2
這個時候我們可以知道 -2 < 0
代表我們需要移動的是左指標,才可以加上更大的數,讓總和更接近0。
因為我們已經排序過這個陣列了

那如果我們遇到相加恰好等於目標總和時,應該要怎麼做?
這題題目要我們要找到所有符合的答案,而非一找到就停止,
所以我們應該要把左指標跟右指標一起移動才對,
這樣對於實作程式碼是不是有想法了?

那我們來討論一下時間複雜度吧!

我們知道要從第一個數開始去檢查到最後面的數,
而每次的基準數檢查都一樣要去確認剩下的數找出符合的兩數,
所以時間複雜度為O(n^2)
空間的複雜度上,因為我們一開始都需要把原本得陣列做排序來使用,
所以空間複雜度O(n)

如果我們依照上面的想法來實作,程式碼如下:

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 sum = array[i] + array[left] + array[right];
        if (sum === targetSum) {
          triplets.push([array[i], array[left], array[right]]);
          left++;
          right--;
        } else if (sum < targetSum) {
          left++;
        } else if (sum > targetSum) {
          right--;
        }
      }
    }
    return triplets;
  }

不過這樣的解法可行的前提是,我們假設原本的陣列每一個數都不一樣。
而以Leetcode這題來說,targetSum = 0 ,所以如果排序完的第一個數是大於0的,
我們其實就可以完全不用繼續檢查了!
且“Notice that the solution set must not contain duplicate triplets.”
-> 不可以含重複的triplets

所以我們要多兩步檢查
1.重複的基準數要跳過
2.左右指針要移動的時候要先檢查下個數有沒有和自己一樣 -> 如果一樣,就要在往前多走一步

完整答案的做法如下:

var threeSum = function (nums) {
    nums.sort((a, b) => a - b);
    const triplets = [];

    for (let i = 0; i < nums.length - 2; i++) {
      if (nums[i] > 0) break;
      if (i > 0 && nums[i] === nums[i - 1]) continue;
      let left = i + 1;
      let right = nums.length - 1;
      while (left < right) {
        const sum = nums[i] + nums[left] + nums[right];
        if (sum === 0) {
          triplets.push([nums[i], nums[left], nums[right]]);
          while (left < right && nums[left] === nums[left + 1]) left++;
          while (left < right && nums[right] === nums[right - 1]) right--;
          left++;
          right--;
        } else if (sum < 0) {
          left++;
        } else if (sum > 0) {
          right--;
        }
      }
    }
    return triplets;
  };

明日題目預告:
Squares of a Sorted Array


上一篇
Day 05 : 來點不一樣的 Two Sum
下一篇
Day 07 : Squares of a Sorted Array
系列文
30天用JavaScript刷題刷起來!30

尚未有邦友留言

立即登入留言