數(shù)組系列
力扣數(shù)據(jù)結(jié)構(gòu)之?dāng)?shù)組-00-概覽
力扣.53 最大子數(shù)組和 maximum-subarray
力扣.128 最長(zhǎng)連續(xù)序列 longest-consecutive-sequence
力扣.167 兩數(shù)之和 II two-sum-ii
力扣.170 兩數(shù)之和 III two-sum-iii
力扣.653 兩數(shù)之和 IV two-sum-IV
力扣.016 最接近的三數(shù)之和 three-sum-closest
力扣.259 較小的三數(shù)之和 three-sum-smaller
題目
給你一個(gè)整數(shù)數(shù)組 nums 配乱，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i != j堪滨、i != k 且 j != k 雷酪，同時(shí)還滿足 nums[i] + nums[j] + nums[k] == 0 。
請(qǐng)你返回所有和為 0 且不重復(fù)的三元組驼抹。
注意：答案中不可以包含重復(fù)的三元組饱岸。
示例 1：
輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
解釋：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 售葡。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 慨绳。
不同的三元組是 [-1,0,1] 和 [-1,-1,2] 。
注意真竖，輸出的順序和三元組的順序并不重要脐雪。
示例 2：
輸入：nums = [0,1,1]
輸出：[]
解釋：唯一可能的三元組和不為 0 。
示例 3：
輸入：nums = [0,0,0]
輸出：[[0,0,0]]
解釋：唯一可能的三元組和為 0 恢共。
提示：
3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
前言
這道題作為 leetcode 的第 15 道題战秋，看起來(lái)似曾相識(shí)。
大概思路可以有下面幾種：
暴力解法
數(shù)組排序+二分
Hash 優(yōu)化
雙指針
v1-暴力解法
思路
直接 3 次循環(huán)讨韭，找到符合結(jié)果的數(shù)據(jù)返回脂信。
這種最容易想到，一般工作中也是我們用到最多的透硝。
當(dāng)然也必定超時(shí)狰闪。
實(shí)現(xiàn)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> res = new HashSet<>();
final int n = nums.length;
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++) {
for(int k = j+1; k < n; k++) {
if(nums[i]+nums[j]+nums[k] == 0) {
List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
Collections.sort(list);
res.add(list);
}
}
}
}
return new ArrayList<>(res);
}
}
效果
超出時(shí)間限制
308 / 313 個(gè)通過(guò)的測(cè)試用例
小結(jié)
這里慢在幾個(gè)地方：
1）三層循環(huán)，找到符合的數(shù)據(jù)
2）數(shù)據(jù)需要去重蹬铺，所以用到了排序尝哆，雖然是一個(gè)小排序。
v2-思維的轉(zhuǎn)換
思路
我們把問(wèn)題這么考慮
要找的數(shù)其實(shí)是：nums[i] + nums[j] + nums[k] == 0
那么甜攀，我們?nèi)绻潭ㄒ粋€(gè)值：
那么問(wèn)題就變成了
nums[j] + nums[k] == -nums[i]
也就是變成了我們的 T001/T167 的題目秋泄。
疑問(wèn) 數(shù)據(jù)去重問(wèn)題呢琐馆？
暫時(shí)先不考慮，過(guò)會(huì)根據(jù)測(cè)試用例優(yōu)化
編程思路
我們定義兩個(gè)指針
left=0
right=n-1
sum=num[left]+num[right-1]
因?yàn)閿?shù)組有有序的恒序，所以只有 3 種情況：
sum == target 直接滿足
sum < target瘦麸，left++
sum > target, right--
實(shí)現(xiàn)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
Set<List<Integer>> res = new HashSet<>();
final int n = nums.length;
// 因?yàn)槭怯行虻模瑥那懊嬲?個(gè)數(shù)字歧胁，等于當(dāng)前數(shù)字更加合理滋饲。
// nums[j] + nums[k] == -nums[i]
for(int i = 0; i < n; i++){
int target = -nums[i];
int left = 0;
int right = n-1;
// 找兩個(gè)數(shù)
while (left < right) {
int sum = nums[left]+nums[right];
if(sum == target) {
// 排序+去重
if(i != left && left != right && i != right) {
List<Integer> list = Arrays.asList(nums[left], nums[right], nums[i]);
Collections.sort(list);
res.add(list);
}
}
if(sum < target) {
left++;
} else {
right--;
}
}
}
return new ArrayList<>(res);
}
}
效果
超出時(shí)間限制 312 / 313 個(gè)通過(guò)的測(cè)試用例
小結(jié)
最大的問(wèn)題還是我們?yōu)槭裁匆ブ兀繛槭裁催@么麻煩
v3-去重
思路
數(shù)據(jù)重復(fù)存在兩個(gè)問(wèn)題：
1）[0, 1, -1] 和 [1, 0, -1] 認(rèn)為重復(fù)
所以我們?cè)诠潭ǖ谝粋€(gè)元素的時(shí)候喊巍，直接跳過(guò) nums[i] == nums[i-1]屠缭，可以解決初始值重復(fù)的問(wèn)題。
2）數(shù)組排序后存在重復(fù)的數(shù)據(jù)崭参，那么我們只需要跳過(guò)重復(fù)的元素即可
我們的 left right 指針移動(dòng)的時(shí)候呵曹，也需要跳過(guò)重復(fù)
初始值的問(wèn)題
我們固定第一個(gè)數(shù) num[i]，下標(biāo)從 0, 1, ..., n-3
剩下的兩個(gè)數(shù)：從 i+1, ..., n-1 中選擇
代碼
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
final int n = nums.length;
for(int i = 0; i < n-2; i++){
// 跳過(guò)重復(fù)的第一個(gè)數(shù)
if(i > 0 && nums[i] == nums[i-1]) {
continue;
}
// 目標(biāo)值
int left = i+1;
int right = n-1;
// 雙指針
while (left < right) {
int sum = nums[i] + nums[left]+nums[right];
if(sum == 0) {
List<Integer> list = Arrays.asList(nums[i], nums[left], nums[right]);
res.add(list);
// 左右避免數(shù)據(jù)重復(fù)
while (left < right && nums[left] == nums[left+1]) {
left++;
}
while (left < right && nums[right] == nums[right-1]) {
right--;
}
}
if(sum < 0) {
left++;
} else {
right--;
}
}
}
return res;
}
效果
32ms 62.27%
效果還行何暮⊙傥梗看了下基本實(shí)現(xiàn)就是這個(gè)。
小結(jié)
這里對(duì)雙指針的理解要求比較高海洼。
而且對(duì)于重復(fù)性數(shù)據(jù)的判斷技巧要求特別高跨新，算得上是一道很接近困難的題目
