LeetCode 之 n 个数之和(Sum n)

LeetCode 中有好几道题是求数字之和的,有 Sum 2Sum 3Sum 4 等。求和这种情况在我们实际开发中也是经常会遇到的,在这不妨拿出来我们把这归并到一起来说说。

无非就是数组中几个数字求和比较是否为目标值。且大多结果中是不能有重复的值。

大致我说下这个题意:

1
2
3
4
5
6
7
8
9
10
11
12
给定一个包含 m 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在 n 个元素,使得这 n 个元素相加的值与 target 相等?找出所有满足条件且不重复的组。

注意:
答案中不可以包含重复的组。

示例:
给定数组 nums = [1, 0, -1, 0, -2, 2], target = 0,n = 4

满足要求的四元组集合为:
[ [-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2] ]

两数之和好办,循环遍历去除重复结果。三数之和也类似。

那要是许多许多数之和呢,遍历就不好使了,那就要采用 BFS 或者 DFS。

答案中不可以包含重复的组从这我们知道,首先,我们需要将数组排个序。

由大化小的思想,我们可以采用 DFS + 回溯来解决这一系列问题。

苦恼不已,别挠头了,我们还是需要好好爱护自己的青青草地!

旨在锻炼逻辑思维,思想对了很重要,请上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
*
* @param nums
* 排序后目标数组
* @param target
* 累加目标数值
* @param k
* 个数
* @param index
* 起始下标
* @return
*/
private ArrayList<List<Integer>> kSum(int[] nums, int target, int k, int index) {

ArrayList<List<Integer>> res = new ArrayList<>();

if (index >= len)
return res;
if (k == 2) { // 两数取和
int i = index, j = len - 1;
while (i < j) {
// 满足条件塞入集合
if (target - nums[i] == nums[j]) {
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[j]);
res.add(temp);
while (i < j && nums[i] == nums[i + 1]) // 跳过重复数值
i++;
while (i < j && nums[j] == nums[j - 1]) // 跳过重复数值
j--;
i++;
j--;
} else if (target - nums[i] > nums[j])
i++;
else
j--;
}
} else {
for (int i = index; i < len - k + 1; i++) {
// 调用递归 DFS
ArrayList<List<Integer>> temp = kSum(nums, target - nums[i], k - 1, i + 1);
// 若是有值返回则将该数塞入,无则不进行任何操作
if (temp != null && temp.size() > 0) {
for (List<Integer> list : temp) {
list.add(nums[i]); // 将满足条件数值塞入
}
res.addAll(temp);
}
while (i < len - 1 && nums[i] == nums[i + 1]) // 跳过重复数值
i++;
}
}
return res;
}

注意:这里 len 定义的是个全局变量,初始值为 0

若 n 为 4,那程序应该是这样的:

1
2
3
4
5
6
7
int len = 0;
public List<List<Integer>> fourSum(int[] nums, int target) {
len = nums.length;
Arrays.sort(nums); // 先排序
return kSum(nums, target, 4, 0); // 递归调用

}

这下只要满足 n > 1 条件的都可以套用这个方法了。

要注意栈的深度。时间换空间。

文章作者: Folgerjun
文章链接: http://putop.top/2018/11/19/leetcode-n-sum/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 DoubleFJ の Blog