數(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è)由 n 個(gè)整數(shù)組成的數(shù)組 nums 苦银，和一個(gè)目標(biāo)值 target 植捎。
請(qǐng)你找出并返回滿足下述全部條件且不重復(fù)的四元組 [nums[a], nums[b], nums[c], nums[d]] （若兩個(gè)四元組元素一一對(duì)應(yīng)典尾，則認(rèn)為兩個(gè)四元組重復(fù)）：
0 <= a, b, c, d < n
a肿嘲、b敲董、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意順序 返回答案 瓦糕。
示例 1：
輸入：nums = [1,0,-1,0,-2,2], target = 0
輸出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
輸入：nums = [2,2,2,2,2], target = 8
輸出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
整體思路
結(jié)合前面我們做 2sum 3sum 的經(jīng)驗(yàn)种远，可能的方式：
暴力
排序+二分
排序+雙指針
Hash 優(yōu)化（局限性比較大）
v1-暴力
思路
直接 4 次 循環(huán)蜜徽，雖然知道等待我們的一定是超時(shí)祝懂。
實(shí)現(xiàn)
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
// 暴力
int count = 0;
for(int i = 0; i < nums1.length; i++) {
for(int j = 0; j < nums2.length; j++) {
for(int k = 0; k < nums3.length; k++) {
for(int l = 0; l < nums4.length; l++) {
int sum = nums1[i] + nums2[j] + nums3[k] + nums4[l];
if(sum == 0) {
count++;
}
}
}
}
}
return count;
}
效果
超出時(shí)間限制
288 / 294 個(gè)通過的測(cè)試用例
小結(jié)
4 次循環(huán)容易想到。但是會(huì)慢在 2 個(gè)地方：
v2-排序+雙指針
思路
結(jié)合我們前面 T015 的方式：
首先固定兩個(gè)位置拘鞋，然后剩下的部分采用雙指針砚蓬。
注意點(diǎn)：
1）需要排除元素的重復(fù)情況
2）固定的 i, j 前兩個(gè)元素都要排除。
其中避免 i 重復(fù)時(shí)盆色，i > 0 && nums[i] == nums[i-1] 跳過
其中避免 j 重復(fù)時(shí)灰蛙，j > i+1 && nums[j] == nums[j-1] 跳過
實(shí)現(xiàn)
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
final int n = nums.length;
for(int i = 0; i < n-3; i++) {
// 跳過重復(fù)的元素
if(i > 0 && nums[i] == nums[i-1]) {
continue;
}
for(int j = i+1; j < n-2; j++) {
if(j > i+1 && nums[j] == nums[j-1]) {
continue;
}
// 雙指針
int left = j+1;
int right = n-1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if(sum == target) {
// 跳過后續(xù)可能重復(fù)的數(shù)據(jù)
List<Integer> list = Arrays.asList(nums[i], nums[j], nums[left], nums[right]);
res.add(list);
// 考慮左邊
while (left < right && nums[left] == nums[left+1]) {
left++;
}
// 右邊
while (left < right && nums[right] == nums[right-1]) {
right--;
}
}
if(sum < target) {
left++;
} else {
right--;
}
}
}
}
return res;
}
}
效果
解答錯(cuò)誤 292 / 294 個(gè)通過的測(cè)試用例
輸入
nums =
[1000000000,1000000000,1000000000,1000000000]
target =
-294967296
添加到測(cè)試用例
輸出
[[1000000000,1000000000,1000000000,1000000000]]
預(yù)期結(jié)果
[]
為什么錯(cuò)誤了
是因?yàn)檫@里越界了，明顯是加入了一個(gè) int 越界的問題隔躲，感覺沒必要摩梧，影響解法整體的美感。
我們調(diào)整一下 sum 的類型宣旱，改為 long仅父。只改下面的一行
從
int sum = nums[i] + nums[j] + nums[left] + nums[right];
改為:
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
效果
17ms 37.37%
小結(jié)
整體這個(gè)類型的題目到這里就告一段落了。
整體只是披著數(shù)組的形式浑吟，本質(zhì)上就是下面幾種：
1）暴力求解
2）排序+二分
3）排序+雙指針
4）Hash 改進(jìn)優(yōu)化
其中 3 的適用性還是比較強(qiáng)的笙纤。
