NSum-Problem

概述

前两天我的好朋友&学弟朱琳同学在网易面试的时候遇到的一个3Sum 问题,然后就引发了这篇 blog.似乎 leetcode,lintcode 这种偏向面试的算法题很喜欢问类似这种问题,所以我在这里尽量把各种类型的 NSum 给大家做个总结.

小声 BB:不得不说人家网站确实做得好,比 oj 强太多了,毕竟是商业项目,但是题目大多是针对面试的,所以哪怕是 hard 难度中的大多数题目其实算法竞赛来说也太过简单了,所以哪怕 oj 那么难用算竞选手还是基本使用 oj 比较多,但是 hard 难度去面试普通岗位感觉已经足够了.另一方面经常用 oj 的话也有利于自己 debug 和思考代码逻辑漏洞的能力,一方面是因为 oj 你 wa 就 wa,而 lintcode 居然都会把你没过的 case数据打印出来给你.总之看需求吧,算法竞赛就找 oj,面试就刷 leetcode,lintcode.

题目连接

先放一下相关题目的连接,主要来自于 leetcode 和 lintcode

two-sum

3sum

3sum-closest

4sum

k-sum

k-sum-ii

其他的相关题目大体类似

解析

two-sum



two-sum这种问题虽然简单但是里面蕴藏了一些思想,这些思想可以帮助我们去解决3sum,4sum 等问题

常见有两种思路

1) 第一种思路是先排序,排序后准备首尾俩指针一前一后逐步缩小范围,时间复杂度排序是O(NlogN),指针移动是O(N),整体时间复杂度O(NlogN)

2) 第二种思路是利用一个简单的等式: 由target = a[i] + a[j] 可以推导得出target - a[j] = a[i],所以实际上你只需要在整个数组中固定一个数a[i],之后看target - a[j]是否存在于数组中即可,时间复杂度O(N)

第二种思路我的 ac 代码

1
2
3
4
5
6
7
8
9
10
11
12
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
Integer index = map.get(target - nums[i]);
if (index != null) {
return new int[]{index, i};
} else {
map.put(nums[i],i);
}
}
return null;
}


这里借助一个辅助空间 map 来实现.talk is cheap,this is code

写到这里我突然想到..其实如果只有语言基础的人的最直接的思路可能就是两层 for 看有没有满足a[i]+a[j]=target的,这种时间复杂度O(N²)了

3Sum



有了 two-sum 的基础,做3sum 就容易很多了,上面1)中提到的思路稍微做一个扩展,当情况是3个数的时候,我们固定一个数,是不是就可以让3Sum 的题目退化成two-sum 了?所以其实这种思路就已经可以解决这种问题了,但是这种思路的代码需要注意跳过重复的情况,因为题目中说结果集合每个元素要唯一.

这个思路需要排序,排序时间复杂度O(NlogN),但是代码时间复杂度是O(N²),可见此时排序已经不是时间复杂度结果的瓶颈.

这个思路我ac的代码

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
class Solution {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (i == 0 || nums[i - 1] != nums[i]) {
int left = i + 1;
int right = nums.length - 1;
int sum = 0 - nums[i];
while (left < right) {
if (nums[left] + nums[right] == sum) {
result.add(Arrays.asList(nums[left], nums[right], nums[i]));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (nums[left] + nums[right] < sum) {
left++;
} else {
right--;
}
}
}
}
return result;
}
}


第二种思路其实就是上面2)的一个扩展,固定一个数a[i],然后 target-a[i]就是新的 target,然后在剩下的数中做 sum-two(hash 法),一样要注意结果不能重复,时间复杂度一样是O(N²),这里也能看出,超过 two-sum 时间瓶颈不再是排序的O(NlogN)之后,双指针法并的时间复杂度并不比用hash法要高,反而是双指针法的空间只需要O(1)显得有一些优势了.

总结一下就是思路继续延续two-sum,只是复杂度稍稍提高一点而已

3sum-closest



思路和3sum 几乎一模一样,只是需要一个额外的中间变量去存储循环过程中最接近 target 的值而已,我的 ac 代码

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
class Solution {
public static int threeSumClosest(int[] nums, int target) {
int sum = 0;
Arrays.sort(nums);
boolean flag = true;
for (int i = 0; i < nums.length - 2; i++) {
if (i == 0 || nums[i - 1] != nums[i]) {
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int result = nums[i] + nums[left] + nums[right];
if (flag) {
sum = result;
flag = false;
}

if (result == target) {
return target;
}
if (Math.abs(result - target) < Math.abs(sum - target)) {
sum = result;
}
if (result < target) {
left++;
} else {
right--;
}
}
}
}
return sum;
}
}


4sum



思路跟3sum 一模一样了..就是加一层 for 循环

整体还是两种思路,一种是先做排序,然后双指针,只是这时候是固定两个数,这种不说了下面有代码

另一种是先排序(必须要排序,才能排除重复)固定两个数作为newTarget(newTarget = target - a[i] - a[j]),然后 map 存储的键是newTarget,然后对下边从 k(k>j && k > i)开始的位置到结束位置做twoSum.这种对应上面的 hash 法,这个我没有实现过.

第一种思路的 ac 代码

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
class Solution {
public static List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++) {
if (i == 0 || nums[i] != nums[i - 1]) {
for (int j = i + 1; j < nums.length - 2; j++) {
if (j == i + 1 || nums[j] != nums[j - 1]) {
int left = j + 1;
int right = nums.length - 1;
int a = target - nums[i] - nums[j];
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == a) {
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[left]);
list.add(nums[right]);
result.add(list);
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (sum > a) {
right--;
} else {
left++;
}

}
}
}
}
}
return result;
}

}


k-sum



学会了什么two-sum,3sum,4sum,你是不是有个想法..能不能写个函数,不管什么 sum 都适用,无非参数里说明一下 k 是几就可以了?

先说一个问题:

> 假设现在有1,2,3…n,n 个数和一个目标和 target,请你输出所有能使得和为 target 的集合

这个问题仔细读一下….这 tm 不是个背包问题嘛..😂

对的..而且是炒鸡简化版的01背包..你不用考虑物品价值.

思路其实很简单,从头开始遍历,无非就是当前的数字放不放进背包里

k-sum就是这种炒鸡简化的背包问题的变种,他要求必须确定 k 的值,而不是 k 是任意值.其实这还是放不放的问题只是有个递推公式dp[i][j][k] = dp[i - 1][j][t] + dp[i - 1][j - 1][t - A[i - 1]],其中t >= A[i - 1],dp[i][j][k]数组的含义是在前i 个元素里选 j 个元素使得他们的结果为 k 的情况有多少种这时候 k-sum 问题的答案就是dp[A.length][k][target]了,上代码

这道题目ac的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 /**
* @param A: An integer array
* @param k: A positive integer (k <= length(A))
* @param target: An integer
* @return: An integer
*/
public int kSum(int[] A, int k, int target) {
int[][][] dp = new int[A.length + 1][k + 1][target + 1];
for (int i = 0; i < A.length; i++)
dp[i][0][0] = 1;

for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= k; j++) {
for (int t = 1; t <= target; t++) {
dp[i][j][t] = dp[i - 1][j][t];
if (t >= A[i - 1]) {
dp[i][j][t] += dp[i - 1][j - 1][t - A[i - 1]];
}
}
}
}
return dp[A.length][k][target];
}


k-sum ii

跟 k-sum 类似,改写成递归的形式写代码更简单,我的 ac 代码如下

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
 /*
* @param A: an integer array
* @param k: a postive integer <= length(A)
* @param target: an integer
* @return: A list of lists of integer
*/
public List<List<Integer>> kSumII(int[] A, int k, int target) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
result(A, A.length - 1, k, target, result, path);
return result;
}

public void result(int[] A, int index, int k, int target, List<List<Integer>> result, List<Integer> path) {
if (target == 0 && k == 0) {
result.add(new ArrayList<>(path));
return;
}
if (index == -1 || target < 0) {
return;
}
path.add(A[index]);
result(A, index - 1, k - 1, target - A[index], result, path);
path.remove(path.size() - 1);
result(A, index - 1, k, target, result, path);
}

上一题如果写成这种递归形式会 TLE,TLE代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    public static int result = 0;

public static int kSum(int[] A, int k, int target) {
kSumOfTarget(A, A.length - 1, target, k);
return result;
}

public static void kSumOfTarget(int[] A, int index, int target, int k) {
if (index < 0 || target <= 0) {
return;
}
if (A[index] == target && k == 1) {
result++;
}
// 放
kSumOfTarget(A, index - 1, target - A[index], k - 1);
// 不放
kSumOfTarget(A, index - 1, target, k);
}
月月说要给我打赏,就还是放了二维码,😝