資訊專欄INFORMATION COLUMN
摘要：如果三個數據相加等于了，就存儲該三個值且更新和指針。邊界條件判斷數組內元素是否都為整數或負數，直接返回。判斷和指針的大小關系。在原來數組上進行排序，不生成副本。
Time：2019/4/3題目三：ADD Two Numbers
Title:3Sum
Difficulty: medium
Author:小鹿
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 循環遍歷所有數據，找出符合條件的數據，時間復雜度為 O(n^3)。能不能更快效率？2、先對數組內數據進行一次排序。O(nlogn)
3、最外層一個 for 循環,先把其中一個值固定住(存放到變量)，然后分別用兩個指針指向數據的非固定值的頭部和尾部，通過 while 循環來遍歷。
4、如果三個數據相加等于 0 了，就存儲該三個值且更新 head 和 end 指針。
5、如果不等于小于或大于 0 ,就更新 head 和 end 指針移動重新查找符合條件的值。
6、返回結果集 result。
1、判斷數組內元素是否都為整數或負數，直接返回。2、判斷固定值、head 以及 end 指針的值前后元素是否相同，去掉重復計算。
3、判斷 head 和 end 指針的大小關系。
4、注意去掉重復數據
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
//用來存取最后結果集
let result = new Array();
//頭指針
let head;
//尾指針
let end;
//固定值
let fixedVal;
//排序
nums.sort((a, b) => {
return a-b;
});
//判斷數組內元素是否都為整數或負數，直接返回
if(nums[0] > 0 || nums[nums.length - 1] < 0) return result;
// 開始遍歷
for (let i = 0; i < nums.length; i++) {
//固定值
fixedVal = nums[i];
// 如果前后元素相同，跳過此次循環（固定值）
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){
//聲明數組，存放這三個值
let group = new Array();
group.push(nums[head]);
group.push(nums[end]);
group.push(fixedVal);
result.push(group);
//存放完畢之后，不要忘記頭指針和尾指針的移動(否則會產生死循環)
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 需要移動頭指針，因為嘗試著讓數據比原有數據大一點
}else if(nums[head] + nums[end] + fixedVal < 0){
head++;
}else{
//否則，尾指針向前移動，讓數據小于元數據
end--;
}
}
}
return result;
}
//測試
let nums = [-1, 0, 1, 2, -1, -4];
threeSum(nums);
定義：sort() 方法用于對數組的元素進行排序。 在原來數組上進行排序，不生成副本。
使用：
1）無參：按照字母的順序對元素排序，即便是數字，先轉換 String 再排序（按照字符編碼），往往得不到我們要的結果。
2）有參：參數為比較函數，比較函數有兩個參數 a,b （默認的 a 是小于 b 的）
若 a 小于 b，在排序后的數組中 a 應該出現在 b 之前，則返回一個小于 0 的值。（從小到大）
若 a 等于 b，則返回 0。（按照無參排序）
若 a 大于 b，則返回一個大于 0 的值。（從大到小）
內部實現：
在 Chrome 瀏覽器中 sort 的你內部實現是快速排序，但是 FireFox 內部使用的歸并排序，兩者的區別就是快速排序不如歸并排序穩定，但是大多數情況下還是可以使用快排的，只有個別要求必須穩定。所謂的穩定性就是原始數據相同的元素在排序之后位置是否改變？
性能問題：
1、sort 會產生性能問題，因為無論是快排還是歸并，都涉及到遞歸，如果遞歸深度過大，導致堆棧溢出，v8 引擎的解決辦法就是設置一個遞歸深度閾值，小于閥值采用插入排序，大于閥值改用快排。
2、快排在在最差的情況下算法也會退化，因為根據 pivot 選擇的不同，最壞情況時間復雜度退化到 O(n^2).
3、怎么進行改進？有興趣可以看下方參考鏈接！
參考鏈接：https://efe.baidu.com/blog/ta...
歡迎一起加入到 LeetCode 開源 Github 倉庫，可以向 me 提交您其他語言的代碼。在倉庫上堅持和小伙伴們一起打卡，共同完善我們的開源小倉庫！
Github：https://github.com/luxiangqia...
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/103231.html
摘要：此專欄文章是對力扣上算法題目各種方法的總結和歸納整理出最重要的思路和知識重點并以思維導圖形式呈現當然也會加上我對導圖的詳解目的是為了更方便快捷的記憶和回憶算法重點不用每次都重復看題解畢竟算法不是做了一遍就能完全記住的所 ...
摘要：排序法復雜度時間空間思路解題思路和一樣，也是先對整個數組排序，然后一個外層循環確定第一個數，然后里面使用頭尾指針和進行夾逼，得到三個數的和。 3Sum Smaller Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 = target){ ...
摘要：本題目的考察點在于函數的格式輸出規則。方法改變隨機數生成器的種子，可以在調用其他隨機模塊函數之前調用此函數。參數改變隨機數生成器的種子。返回一個至區間包含和的整數。 ...
摘要：給定一個包含個整數的數組，判斷中是否存在三個元素，，，使得找出所有滿足條件且不重復的三元組。 給定一個包含 n 個整數的數組?nums，判斷?nums?中是否存在三個元素 a，b，c ，使得?a + b + c = 0 ？找出所有滿足條件且不重復的三元組。 注意：答案中不可以包含重復的三元組。 例如, 給定數組 nums = [-1, 0, 1, 2, -1, -4]， 滿足要求的三元...
摘要：三數之和給定一個包含個整數的數組，判斷中是否存在三個元素，，，使得找出所有滿足條件且不重復的三元組。例如給定數組，滿足要求的三元組集合為答案參考 LeetCode15.三數之和 JavaScript 給定一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重復的三元組。 注意：答案中不可以包含重...
閱讀 1602·2021-09-30 09:47
閱讀 3598·2021-09-22 15:05
閱讀 2840·2021-08-30 09:44
閱讀 3624·2019-08-30 15:55
閱讀 1373·2019-08-30 13:08
閱讀 1330·2019-08-29 16:40
閱讀 553·2019-08-29 12:45
閱讀 1390·2019-08-29 11:25
