LeetCode 之 JavaScript 解答第十五題 —— 三數(shù)之和（3Sum）

Wildcard 發(fā)布于2019-08-23 16:45 / 2429人閱讀

摘要：如果三個數(shù)據(jù)相加等于了，就存儲該三個值且更新和指針。邊界條件判斷數(shù)組內(nèi)元素是否都為整數(shù)或負數(shù)，直接返回。判斷和指針的大小關(guān)系。在原來數(shù)組上進行排序，不生成副本。

Time：2019/4/3
Title:3Sum
Difficulty: medium
Author:小鹿

題目三：ADD Two Numbers

Given an array?nums?of?n?integers, are there elements?a,?b,?c?in?nums?such that?a?+?b?+?c?= 0? Find all unique triplets in the array which gives the sum of zero.

Note:
The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solve:

▉ 算法思路：

1、直接用三個 for 循環(huán)遍歷所有數(shù)據(jù)，找出符合條件的數(shù)據(jù)，時間復(fù)雜度為 O(n^3)。能不能更快效率？2、先對數(shù)組內(nèi)數(shù)據(jù)進行一次排序。O(nlogn)
3、最外層一個 for 循環(huán),先把其中一個值固定住(存放到變量)，然后分別用兩個指針指向數(shù)據(jù)的非固定值的頭部和尾部，通過 while 循環(huán)來遍歷。
4、如果三個數(shù)據(jù)相加等于 0 了，就存儲該三個值且更新 head 和 end 指針。
5、如果不等于小于或大于 0 ,就更新 head 和 end 指針移動重新查找符合條件的值。
6、返回結(jié)果集 result。

▉ 邊界條件：

1、判斷數(shù)組內(nèi)元素是否都為整數(shù)或負數(shù)，直接返回。2、判斷固定值、head 以及 end 指針的值前后元素是否相同，去掉重復(fù)計算。
3、判斷 head 和 end 指針的大小關(guān)系。
4、注意去掉重復(fù)數(shù)據(jù)

▉ 代碼實現(xiàn)：

  /**
  * @param {number[]} nums
  * @return {number[][]}
  */

var threeSum = function(nums) {
    //用來存取最后結(jié)果集
    let result = new Array();
    //頭指針
    let head;
    //尾指針
    let end;
    //固定值
    let fixedVal;

    //排序
    nums.sort((a, b) => {
        return a-b;
    });
    
    //判斷數(shù)組內(nèi)元素是否都為整數(shù)或負數(shù)，直接返回
    if(nums[0] > 0 || nums[nums.length - 1] < 0) return result;
    
    // 開始遍歷
    for (let i = 0; i < nums.length; i++) {
        //固定值
        fixedVal = nums[i];
        // 如果前后元素相同，跳過此次循環(huán)（固定值）
        if(fixedVal === nums[i-1]) continue;
        //一開始的固定值為nums[0],所以頭指針為 i+1 下一個元素
        head = i+1;
        //尾指針
        end = nums.length - 1;
        //如果頭指針小于尾指針元素
        while(head < end){
            //判斷固定值+頭指針+尾指針是否等于0
            if(nums[head] + nums[end] + fixedVal === 0){
                //聲明數(shù)組，存放這三個值
                let group =  new Array();
                group.push(nums[head]);
                group.push(nums[end]);
                group.push(fixedVal);
                result.push(group);
                //存放完畢之后，不要忘記頭指針和尾指針的移動(否則會產(chǎn)生死循環(huán))
                head += 1;
                end -= 1;
                //如果頭指針滿足小于尾指針且移動后的指針和移動前的指針元素相等，再往前移動
                while(head < end && nums[head] === nums[head - 1]){
                    head += 1;
                }
                 //如果頭指針滿足小于尾指針且移動后的指針和移動前的指針元素相等，再往后移動
                while(head < end && nums[end] === nums[end + 1]){
                    end -= 1;
                }
             //小于 0 需要移動頭指針，因為嘗試著讓數(shù)據(jù)比原有數(shù)據(jù)大一點
            }else if(nums[head] + nums[end] + fixedVal < 0){
                head++;
            }else{
                //否則，尾指針向前移動，讓數(shù)據(jù)小于元數(shù)據(jù)
                end--;
            }
        } 
    }
    return result;
}
//測試
let nums = [-1, 0, 1, 2, -1, -4];
threeSum(nums);

▉ sort 排序：

定義：sort() 方法用于對數(shù)組的元素進行排序。 在原來數(shù)組上進行排序，不生成副本。
使用：
1）無參：按照字母的順序?qū)υ嘏判颍幢闶菙?shù)字，先轉(zhuǎn)換 String 再排序（按照字符編碼），往往得不到我們要的結(jié)果。
2）有參：參數(shù)為比較函數(shù)，比較函數(shù)有兩個參數(shù) a,b （默認的 a 是小于 b 的）

若 a 小于 b，在排序后的數(shù)組中 a 應(yīng)該出現(xiàn)在 b 之前，則返回一個小于 0 的值。（從小到大）
若 a 等于 b，則返回 0。（按照無參排序）
若 a 大于 b，則返回一個大于 0 的值。（從大到小）

內(nèi)部實現(xiàn)：
在 Chrome 瀏覽器中 sort 的你內(nèi)部實現(xiàn)是快速排序，但是 FireFox 內(nèi)部使用的歸并排序，兩者的區(qū)別就是快速排序不如歸并排序穩(wěn)定，但是大多數(shù)情況下還是可以使用快排的，只有個別要求必須穩(wěn)定。所謂的穩(wěn)定性就是原始數(shù)據(jù)相同的元素在排序之后位置是否改變？
性能問題：
1、sort 會產(chǎn)生性能問題，因為無論是快排還是歸并，都涉及到遞歸，如果遞歸深度過大，導(dǎo)致堆棧溢出，v8 引擎的解決辦法就是設(shè)置一個遞歸深度閾值，小于閥值采用插入排序，大于閥值改用快排。
2、快排在在最差的情況下算法也會退化，因為根據(jù) pivot 選擇的不同，最壞情況時間復(fù)雜度退化到 O(n^2).
3、怎么進行改進？有興趣可以看下方參考鏈接！
參考鏈接：https://efe.baidu.com/blog/ta...