# 漫画：经典鹅厂面试题（4sum - nSum）

01

PART

[

[-1, 0, 0, 1],

[-2, -1, 1, 2],

[-2, 0, 0, 2]

]

02

PART

```for (int i = 0; i < n - 3; i++) {
//特殊处理-1
if (i > 0 && nums[i] == nums[i - 1]) continue;
if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
if (nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;
for (int j = i + 1; j < n - 2; j++) {
//特殊处理-2
if (j - i > 1 && nums[j] == nums[j - 1]) continue;
if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
if (nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target) continue;
int left = j + 1;
int right = n - 1;
while (left < right) {
//双指针循环查找
}
}
```

• 第 3 行和第 8 行分别处理了 i 和 j 重复值的情况。
• 第 4-5 和 9-10 就是我们上面说的，利用排序的特性，直接过滤掉重复计算了。

```//JAVA
while (left < right) {
int tmp = nums[i] + nums[j] + nums[left] + nums[right];
if (tmp == target) {
List<Integer> tmpList = new LinkedList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left += 1;
while (left < right && nums[right] == nums[right - 1]) right -= 1;
left += 1;
right -= 1;
} else if (tmp > target) right -= 1;
else left += 1;
}
```

```//JAVA
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
if (nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;
for (int j = i + 1; j < n - 2; j++) {
if (j - i > 1 && nums[j] == nums[j - 1]) continue;
if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
if (nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target) continue;
int left = j + 1;
int right = n - 1;
while (left < right) {
int tmp = nums[i] + nums[j] + nums[left] + nums[right];
if (tmp == target) {
List<Integer> tmpList = new LinkedList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left += 1;
while (left < right && nums[right] == nums[right - 1]) right -= 1;
left += 1;
right -= 1;
} else if (tmp > target) right -= 1;
else left += 1;
}
}

}
return res;
}
}
```

```//JAVA
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
for (int i = 0; i < n - 3; i++) {
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 tmp = nums[i] + nums[j] + nums[left] + nums[right];
if (tmp == target) {
List<Integer> tmpList = new LinkedList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left += 1;
while (left < right && nums[right] == nums[right - 1]) right -= 1;
left += 1;
right -= 1;
} else if (tmp > target) right -= 1;
else left += 1;
}
}
}
return res;
}
}
```

• 本系列所有教程都不会用到复杂的语言特性，大家无须担心没有学过相关语法，算法思想才是最重要的！
• 作为学术文章，虽然风格可以风趣，但严谨，我是认真的。本文所有代码均在leetcode进行过测试运行。

03

PART

2sum，3sum，4sum 系列篇 到这里就结束了。这里边 2sum 和 3sum 还是非常建议大家去练习一下的。算法这个东西，思想是一回事，动手是另一回事。长路漫漫磕磕绊绊，难受就是提高。

0 条评论

• ### 漫画：常考的荷兰国旗问题你还不会吗？（初级）

"荷兰国旗问题" 是计算机科学中的一个经典题目，它是由Edsger Dijkstra提出的。荷兰国旗由红、白、蓝三色组成。

• ### 漫画：经典鹅厂面试题（2Sum，3Sum，4Sum）

该题为 二数之和 的进阶版本，当然还有一个进阶版本为 四数之和。我们将会一一进行分析！

• ### 漫画：美团面试题（TOPK：求第K个最大的元素）

这个题目的变形很多，比如找 "前 K 个高频元素"、 "数据流中的第K大元素" 、"最接近原点的 K 个值" 等等等等。

• ### 双指针法：一样的道理，能解决四数之和

题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c ...

• ### LeetCode-15 三数之和

今天我们学习第15题三数之和，这是一道中等题。像这样字符串的题目经常作为面试题来考察面试者算法能力和写代码能力，因此最好能手写出该题。下面我们看看这道题...

• ### LeetCode-18 四数之和

今天我们学习第18题四数之和，这是一道中等题。像这样数组的题目经常作为面试题来考察面试者算法能力和写代码能力，因此最好能手写出该题。下面我们看看这道题的...

• ### Python3刷题系列（三）

中文版：https://leetcode-cn.com/problems/sqrtx/

• ### 【python-leetcode15-双指针】三个数之和为零

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组...

• ### 漫画：经典鹅厂面试题（2Sum，3Sum，4Sum）

该题为 二数之和 的进阶版本，当然还有一个进阶版本为 四数之和。我们将会一一进行分析！

• ### LeetCode-31-Next-Permutation

这个排序主要是有两种情况，一个是类似于3 1 2这样的情况，直接从后往前找到第一个nums[i]<nums[i-1]的，然后把i记下来，再与后面第一个小于i的k...