今天分享一个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, 0, 4],看下面的代码,建造去重的容器会比较好做,也减少内部的计算量。
// 预处理,排序
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;
}
});
首先创建两个控制下标的,如下图所示黑色坐标和红色坐标,目的是遍历所有两数之和:
file
直到黑色坐标大于等于下标2时,如下图,可以从散列表现有的key去进行比较,target = 4,则将查找target - key = 4 - (-2 + 0) = 6,查找时间复杂度是O(1),查找非常快。如果没有查找到则继续红色坐标的移动。
file
如果查找到,如下图:
file
因为四个下标随便两两交换都会产生重复的四元组,可以固定四个下标产生一个唯一性的四元组。所以我特定将黑色下标固定第三个,红色下标固定第四个,那第二个下标不可大于等于黑色下标,代码可这样写:
// 控制四个下标
if (map.containsKey(target - key)) {
for (List<Integer> tuple : map.get(target - key)) {
// 下标去重
if (tuple.get(1) < i) {
// code
}
}
}
但是这远远不够,还需要考虑输入数据的重复问题,如下图:
file
下标5和下标6的数据是重复的,如果找到了散列表的目标值,而且黑色下标的值比目标值的value要大,就要除掉后面输入数据的重复数据,不能再出现重复的四元组了。所以在前面创建了去重的容器,如下图:
file
如果还要为了减少计算,可以往前推点,有什么好的idea靠你们了。
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()));
}
执行用时 : 54 ms, 在所有 Java 提交中击败了 17.11% 的用户
内存消耗 : 42.7 MB, 在所有 Java 提交中击败了 10.27% 的用户
呃,这结果还不如暴力法来的直接。自罚自罚,把排第一的代码画成动画出来。
双指针在有数组的题会比较常见,而且数组 + 双指针 + 排序就决胜大多数的数据结构。
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;
}
-END-