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