【leetcode】ksum 求符合条件的 k 个数

1. Two Sum 两数之和

题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

思路

最简单粗暴的一个双层循环：

（1）遍历第一层数组 nums[i]

（2）遍历第二层数组 nums[j]，如果 nums[i] + nums[j] == t，符合。

基础解法

java 实现：

性能分析：

可谓惨不忍睹，为什么呢？

是否有比较好的优化思路？

优化解法

优化思路：

借助 HashMap 数据结构，将原本 O(n) 的遍历，降低为 O(1) 的查询。

java 实现如下：

实现时注意 HashMap 的扩容问题，此处直接指定为和数组一样大。

效果：

15. 3Sum 三数之和

结束了第一道开胃菜之后，我们来看看第二道菜。

题目

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

注意：答案中不可以包含重复的三元组。

示例：

粗暴解法

最简单的思路，我们直接来一个三层循环：

•执行结果

很不幸，这个是不通过的。会执行超时，因为执行的比较慢。

优化解法

优化思路：

（1）对原始数组进行排序，保证可以使用双指针法

（2）固定 1 个元素。剩余的两个元素采用双指针的方式。初始化时，一个在最左边，一个在最右边。然后不断调整位置，直到符合条件为止。

（3）不可以包含重复的三元组，要同时跳过重复的信息。

java 实现：

性能：

速度超过 99.87 的用户提交，还不错。

16. 最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。

请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

示例 2：

提示：

3

-1000

-10^4

V1-双指针法

思路

针对多个数之和，对无序的数组进行一次排序，可以大大降低后续的时间复杂度。

我们通过两个指针，l r 分别计算每一次的差值，找到最小的差异。

当然，等于肯定最小，直接返回即可。

java 实现

效果

效果还是非常不错的。

V2-优化

思路

针对上面的算法进行优化。

能否继续借助排序+双指针？

1.

最大值如果依然小于原有差异，跳过

2.

最小值如果依然大于原有差异，跳过。

直接先把可能有结果的大概范围找到，然后再进一步细化，快速定位结果。

java 实现

效果

18. 4Sum 四数之和

常言道，有二有三必须有四。

这道题当然还有四个数之和的版本。

题目

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

解法

解题思路类似上述的 3 个数之和，区别是这次我们固定左边 2 个元素。

java 实现如下：

经过 3sum 之后，你对自己的实现信心十足。

效果对比打败了 49.10% 的用户。WTF!

其实答案也很简单，因为大家和你一样已经学会了这种解法。

那么，我们还能优化吗？

优化方法

思路：

主要是可以快速返回的一些优化

（1）对于长度小于 4 的数组，直接返回

（2）如果在当前循环中 max 小于 target，或者 min 大于 target 其实也可以快速跳过。

java 实现：

效果：

超过了 92.32% 的提交，勉强过关。

ksum

题目

经过了上面的 2sum/3sum/4sum 的洗礼，我们现在将这道题做下推广。

如何求 ksum？

思路

其实所有的这种解法都可以转换为如下的两个问题：

（1）sum 问题

（2）将 k sum 问题转换为 k-1 sum 问题

示例代码

开源地址

为了便于大家学习，所有实现均已开源。欢迎 fork + star~

https://github.com/houbb/leetcode

参考资料

https://leetcode-cn.com/problems/two-sum

https://leetcode.com/problems/two-sum/discuss/3/Accepted-Java-O(n)-Solution

https://leetcode-cn.com/problems/3sum

https://leetcode-cn.com/problems/4sum

https://leetcode.com/problems/4sum/discuss/8609/My-solution-generalized-for-kSums-in-JAVA