LeetCode 图解 | 18.四数之和
作者我脱下短袖
来源：算法无遗策
今天分享的题目来源于 LeetCode 第 18 号题：四数之和，题目标签是：散列表、双指针和数组。
题目描述
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
题目解析
还是老习惯，看一个题没有想到一个好的思路，去看题目标签包含哪种标签。 此题的题目标签是散列表、双指针和数组。
那就先从散列表开始入手，双指针会在文章后面重新介绍一个代码出来。
散列表
从散列表入手，先看看输入数据是怎样的数据，如果是只含字母的字符串，用直接寻址表可以试试的，如果是小数点或负数或范围比较大的数字，用归约化处理可以试试，但俺这里就不想麻烦了，直接用 散列表 吧。
回到这个题，俺之前考虑过不使用开头就排序好的数据，也想过使用空间换时间的方法，也使用过多个辅助散列表去标记，但是都败在重复的数据。即使开头不排序直接用散列表，也要从内部消耗大量的计算，不如一开头排序计算量地少。
蛋疼，难道是修为不够，遗漏了哪个idea没想到？
为自罚，我把通过双指针的代码也画成动画了出来了，文章后面会介绍双指针和算法动画。
用散列表通过之后又去看了排行榜排前面的代码，都是 数组+双指针 控制下标。
假设输入示例：[-5, 5, 4, -3, 0, 0, 4, -2]，target = 4 不预先排序，直接用散列表，将所有的两数求和设为 key，两数的下标组为 value 。如 -5 + 5 = 0，key 为 0 ，value 为[[0, 1], [4, 5]]。
如果要找到满足条件的四元组，将 target - key = 4 - (0) = 4，key 为 4 ，对应的 value 为 [[2, 4], [4, 6]] 。
[[0, 1], [4, 5]] 和 [[2, 4], [4, 6]] 所有满足四元组的下标组是[0, 1, 2, 4] 和 [0, 1, 4, 6]，对应的四元组是[-5, 5, 0, 4], [-5, 5, 4, 0]，然后如何让这四元组去重呢？
如果是要排序比较或者看看是否包含，都不如一开始预先排序的好，俺也用过用散列表的同时去创建辅助散列表，去统计数据重复的个数，但是也不行。
照样也会出现重复的四元组。
可能有同学会问了，让四元组的下标组去重不就可以了吗？下标数组去重并不能说明四元数组也能去重，除非输入示例没有重复的数据。
如果做了预处理排序，到最后产生的四元组会变成 [-5, 5, 0, 4] 和 [-5, 5, 4, 0]，看下面的代码，建造去重的容器会比较好做，也减少内部的计算量。
// 预处理，排序
Arrays.sort(nums);
// 建立去重的容器
Set<List<Integer>> result_set = new TreeSet<>(new Comparator<List<Integer>>() {
@Override
public int compare(List<Integer> o1, List<Integer> o2) {
for (int i = 0; i < o1.size(); i++) {
if (!o1.get(i).equals(o2.get(i))) return o1.get(i) - o2.get(i);
}
return 0;
}
});
首先创建两个控制下标的，如下图所示黑色坐标和红色坐标，目的是遍历所有两数之和：
直到黑色坐标大于等于下标 2 时，如下图，可以从散列表现有的 key 去进行比较，target = 4，则将查找target - key = 4 - (-2 + 0) = 6，查找时间复杂度是 O(1)，查找非常快。
如果没有查找到则继续红色坐标的移动。
如果查找到，如下图：
因为四个下标随便两两交换都会产生重复的四元组，可以固定四个下标产生一个唯一性的四元组。
所以我特定将黑色下标固定第三个，红色下标固定第四个，那第二个下标不可能会大于黑色下标，代码可这样写：
// 控制四个下标
if (map.containsKey(target - key)) {
for (List<Integer> tuple : map.get(target - key)) {
// 下标去重
if (tuple.get(1) < i) {
// code
}
}
}
但是这远远不够，还需要考虑输入数据的重复问题，如下图：
下标 5 和下标 6 的数据是重复的，如果找到了散列表的目标值，而且黑色下标的值比目标值的 value 要大，就要除掉后面输入数据的重复数据，不能再出现重复的四元组了。所以在前面创建了去重的容器，如下图：
动画描述
参考代码
public List<List<Integer>> fourSum(int[] nums, int target) {
// 建立收集下标的散列表
Map<Integer, List<List<Integer>>> map = new HashMap();
// 返回答案
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length < 4) return result;
Arrays.sort(nums);
// 建立去重的容器
Set<List<Integer>> result_set = new TreeSet<>(new Comparator<List<Integer>>() {
@Override
public int compare(List<Integer> o1, List<Integer> o2) {
for (int i = 0; i < o1.size(); i++) {
if (!o1.get(i).equals(o2.get(i))) return o1.get(i) - o2.get(i);
}
return 0;
}
});
// 将nums的两键相加添加到散列表
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
int key = nums[i] + nums[j];
// 在这里将结果添加到result
if (map.containsKey(target - key)) {
for (List<Integer> tuple : map.get(target - key)) {
// 下标去重
if (tuple.get(1) < i) {
List<Integer> res = new ArrayList<>();
res.add(nums[tuple.get(0)]);
res.add(nums[tuple.get(1)]);
res.add(nums[i]);
res.add(nums[j]);
result_set.add(res);
}
}
}
// key若不在散列表则赋予新的空间
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
List<Integer> e = new ArrayList<>(2); // 数组容量为2
e.add(i);
e.add(j);
map.get(key).add(e);
}
}
result.addAll(result_set);
return result;
}
public static void main(String[] args) {
int[] nums = {1, 0, -1, 0, -2, 2};
List<List<Integer>> result = new Solution().fourSum(nums, 0);
System.out.println(Arrays.deepToString(result.toArray()));
}
双指针
双指针在有数组的题会比较常见，而且数组 + 双指针 + 排序就决胜大多数的数据结构。
动画描述
参考代码
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length < 4) return result;
Arrays.sort(nums);
int length = nums.length;
//第一层循环k
for (int k = 0; k < length - 3; k++) {
if (k > 0 && nums[k] == nums[k -1]) continue;
//判断最小值最大值和target比较大小
int min1 = nums[k] + nums[k + 1] + nums[k + 2] + nums[k + 3];
if (min1 > target) break;
int max1 = nums[k] + nums[length - 3] + nums[length - 2] + nums[length - 1];
if (max1 < target) continue;
//第二层循环i
for (int i = k + 1; i < length - 2; i++) {
if (i > k + 1 && nums[i] == nums[i - 1]) continue;
//定义双指针j,h
int j = i + 1;
int h = length - 1;
//判断最小值最大值和target比较大小
int min = nums[k] + nums[i] + nums[j] + nums[j + 1];
if (min > target) continue;
int max = nums[k] + nums[i] + nums[h -1] + nums[h];
if (max < target) continue;
//开始双指针j,h
while (j < h) {
int curr = nums[k] + nums[i] + nums[j] + nums[h];
if (curr == target) {
result.add(Arrays.asList(nums[k], nums[i], nums[j], nums[h]));
j++;
while (j < h && nums[j] == nums[j -1]) {
j++;
}
h--;
while (j < h && nums[h] == nums[h + 1]) {
h--;
}
} else if (curr > target) {
h--;
} else {
j++;
}
}
}
}
return result;
}