做过leetcode的人都知道, 里面有2sum, 3sum(closest), 4sum等问题, 这些也是面试里面经典的问题, 考察是否能够合理利用排序这个性质, 一步一步得到高效的算法. 经过总结, 本人觉得这些问题都可以使用一个通用的K sum求和问题加以概括消化, 这里我们先直接给出K Sum的问题描述和算法(递归解法), 然后将这个一般性的方法套用到具体的K, 比如leetcode中的2Sum, 3Sum, 4Sum问题. 同时我们也给出另一种哈希算法的讨论.
leetcode求和问题描述(K sum problem):
K sum的求和问题一般是这样子描述的:给你一组N个数字(比如 vector<int> num), 然后给你一个常数(比如 int target) ,我们的goal是在这一堆数里面找到K个数字,使得这K个数字的和等于target。
注意事项(constraints):
注意这一组数字可能有重复项:比如 1 1 2 3 , 求3sum, 然后 target = 6, 你搜的时候可能会得到 两组1 2 3, 1 2 3,1 来自第一个1或者第二个1, 但是结果其实只有一组,所以最后结果要去重。
K Sum求解方法, 适用leetcode 2Sum, 3Sum, 4Sum:
方法一:暴力,就是枚举所有的K-subset, 那么这样的复杂度就是 从N选出K个,复杂度是O(N^K)
方法二:排序,这个算法可以考虑最简单的case, 2sum,这是个经典问题,方法就是先排序,然后利用头尾指针找到两个数使得他们的和等于target,
这个2sum算法网上一搜就有,这里不赘述了,给出2sum的核心代码:
03
|
int j
= num.size() - 1;
|
05
|
int sum
= num[i] + num[j];
|
07
|
store
num[i] and num[j] somewhere;
|
08
|
if (we
need only one such pair of numbers)
|
2sum的算法复杂度是O(N log N) 因为排序用了N log N以及头尾指针的搜索是线性的,所以总体是O(N log N),好了现在考虑3sum, 有了2sum其实3sum就不难了,这样想:先取出一个数,那么我只要在剩下的数字里面找到两个数字使得他们的和等于(target – 那个取出的数)就可以了吧。所以3sum就退化成了2sum, 取出一个数字,这样的数字有N个,所以3sum的算法复杂度就是O(N^2 ), 注意这里复杂度是N平方,因为你排序只需要排一次,后面的工作都是取出一个数字,然后找剩下的两个数字,找两个数字是2sum用头尾指针线性扫,这里很容易错误的将复杂度算成O(N^2
log N),这个是不对的。我们继续的话4sum也就可以退化成3sum问题,那么以此类推,K-sum一步一步退化,最后也就是解决一个2sum的问题,K sum的复杂度是O(n^(K-1))。 这个界好像是最好的界了,也就是K-sum问题最好也就能做到O(n^(K-1))复杂度,之前有看到过有人说可以严格数学证明,这里就不深入研究了。
K Sum (2Sum, 3Sum, 4Sum) 算法优化(Optimization):
这里讲两点,第一,注意比如3sum的时候,先整体排一次序,然后枚举第三个数字的时候不需要重复, 比如排好序以后的数字是 a b c d e f, 那么第一次枚举a, 在剩下的b c d e f中进行2 sum, 完了以后第二次枚举b, 只需要在 c d e f中进行2sum好了,而不是在a c d e f中进行2sum, 这个大家可以自己体会一下,想通了还是挺有帮助的。第二,K Sum可以写一个递归程序很优雅的解决,具体大家可以自己试一试。写递归的时候注意不要重复排序就行了。
K Sum (2Sum, 3Sum, 4Sum) 算法之3sum源代码(不使用std::set)和相关开放问题讨论:
因为已经收到好几个网友的邮件需要3sum的源代码, 那么还是贴一下吧, 下面的代码是可以通过leetcode OJ的代码(又重新写了一遍, 于Jan, 11, 2014 Accepted), 就当是K sum的完整的一个case study吧, 顺便解释一下上面的排序这个注意点, 同时我也有关于结果去重的问题可以和大家讨论一下,
也请大家集思广益, 发表意见, 首先看源代码如下:
03
|
vector<vector< int >
> threeSum(vector< int >
&num) {
|
04
|
vector<vector< int >
> vecResult;
|
08
|
vector< int >
vecTriple(3, 0);
|
09
|
sort(num.begin(),
num.end());
|
10
|
int iCurrentValue
= num[0];
|
11
|
int iCount
= num.size() - 2;
|
12
|
for ( int i
= 0; i < iCount; ++i) {
|
13
|
if (i
&& num[i] == iCurrentValue) {
|
17
|
vecTriple[0]
= num[i];
|
19
|
int k
= num.size() - 1;
|
21
|
int iSum
= num[j] + num[k];
|
22
|
if (iSum
+ vecTriple[0] == 0) {
|
23
|
vecTriple[1]
= num[j];
|
24
|
vecTriple[2]
= num[k];
|
25
|
vecResult.push_back(vecTriple);
|
29
|
else if (iSum
+ vecTriple[0] < 0)
|
34
|
iCurrentValue
= num[i];
|
38
|
vector<
vector< int >
>::iterator it = unique(vecResult.begin(), vecResult.end());
|
39
|
vecResult.resize(
distance(vecResult.begin(), it) );
|
首先呢, 在K Sum问题中都有个结果去重的问题, 前文也说了, 如果输入中就有重复元素的话, 最后结果都需要去重, 去重有好几个办法, 可以利用std::set的性质(如leetcode上3sum的文章, 但是他那个文章的问题是, set没用好, 导致最终复杂度其实是O(N^2 * log N), 而非真正的O(N^2) ), 可以利用排序(如本文的方法)等, 去重本身不难, 难的是不利用任何排序或者std::set直接得到没有重复的triplet结果集. 本人试图通过已经排好序这个性质来做到这一点(试图不用trick
3和4下面的两条语句), 但是经过验证这样的代码(没有trick 3, 4下面的两行代码, 直接return vecResult)也不能保证结果没有重复,于是不得不加上了trick 3, 4,还是需要通过在结果集上进一步去重.笔者对于这个问题一直没有很好的想法,希望这里的代码能抛砖引玉,
大家也讨论一下有没有办法, 或者利用排序的性质或者利用其它方法, 直接得到没有重复元素的triplet结果集, 不需要去重这个步骤.
那么还是解释一下源代码里面有四个trick,以及笔者试图不利用任何std::set或者排序而做到去重的想法.
第一个无关紧要顺带的小trick 1, 是说我们排好序以后, 只需要检测到倒数第三个数字就行了, 因为剩下的只有一种triplet 由最后三个数字组成. 接下来三个trick都是和排序以及最后结果的去重问题有关的, 我一起说.
笔者为了达到不需要在最后的结果集做额外的去重, 尝试了以下努力: 首先对输入数组整体排序, 然后使用之前提到的3sum的算法, 每次按照顺序先定下triplet的第一个数字, 然后在数组后面寻找2sum, 由于已经排好序, 为了防止重复, 我们要保证triplet的第一个数字没有重复, 举个例子, -3, – 3, 2, 1, 那么第二个-3不应该再被选为我们的第一个数字了,因为在第一个-3定下来寻找2
sum的时候, 我们一定已经找到了所有以-3为第一个数字的triplet(trick 2).但是这样做尽管可以避免一部分的重复, 但是还有另一种重复无法避免: -3, -3, -3, 6, 那么在定下第一个-3的时候, 我们已经有两组重复triplet <-3, -3, 6>, 如何在不使用std::set的情况下避免这类重复, 笔者至今没有很好的想法.大家有和建议?
望不吝赐教!
Hash解法(Other):
其实比如2sum还是有线性解法的,就是用hashmap, 这样你check某个值存在不存在就是常数时间,那么给定一个sum, 只要线性扫描, 对每一个number判断sum – num存在不存在就可以了。注意这个算法对有重复元素的序列也是适用的。比如 2 3 3 4 那么hashtable可以使 hash(2) = 1;hash(3) = 1, hash(4) =1其他都是0, 那么check的时候,扫到两次3都是check sum – 3在不在hashtable中,注意最后返回所有符合的pair的时候也还是要去重。这样子推广的话
3sum 其实也有O(N^2)的类似hash算法,这点和之前是没有提高的,但是4sum就会有更快的一个算法。
4sum的hash算法:
O(N^2)把所有pair存入hash表,并且每个hash值下面可以跟一个list做成map, map[hashvalue] = list,每个list中的元素就是一个pair, 这个pair的和就是这个hash值,那么接下来求4sum就变成了在所有的pair value中求 2sum,这个就成了线性算法了,注意这里的线性又是针对pair数量(N^2)的线性,所以整体上这个算法是O(N^2),而且因为我们挂了list, 所以只要符合4sum的我们都可以找到对应的是哪四个数字。
到这里为止有人提出这个算法不对 (感谢Jun提出这点!! See the comment below), 因为这里的算法似乎无法检查取出来的四个数字是否有重复的, 也就是说在转换成2sum问题得到的那些个pair中, 有可能会有重复元素, 比如说原来数组中的第一个元素其实是重复了两次才使得4 sum满足要求, 那么这样得到的四元组(四个数字的和等于给定的值), 其实只有三个原数组元素, 其中第一个元素用了两次, 那么这样就不对了. 如果仅从我上面的描述来看, 确实是没有办法检查重复的, 但是仔细想想我们只要在map中存pair的的时候记录下的不是原数组对应的值,
而是原数组的id,就可以避免这个问题了. 更加具体的, map[hashvalue] = list, 每个list的元素就是一个pair, 这个pair<int, int> 中的pair是原来的array id, 使得这两个id对应到元素组中的元素值的和就是这个hash值. 那么问题就没有了, 我们在转换成的2sum寻找所有pair value的2sum的同时要检查最后得到的四元组<id1, id2, id3, id4>没有重复id. 这样问题就解决了.
结束语:
这篇文章主要想从一般的K sum问题的角度总结那些比较经典的求和问题比如leetcode里面的2sum, 3sum(closest), 4sum等问题, 文章先直接给出K Sum的问题描述和算法(递归解法), 然后将这个一般性的方法套用到具体的K, 比如leetcode中的2Sum, 3Sum, 4Sum问题. 同时我们也给出另一种哈希算法的讨论.那么这篇文章基本上还是自己想到什么写什么,有疏忽不对的地方请大家指正,也欢迎留言讨论,如果需要源代码,请留言或者发邮件到info@tech-wonderland.net
分享到:
相关推荐
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
leetcode 2 和 c 力码 为准备面试做 leetcode 问题。 第 1 天 (5/24/2020) 双指针 第167章 二和二(简单) ##python solution class Solution : def twoSum ( self , numbers : List [ int ], target : int ) -> ...
leetcode打不开Leetcode Note Tips Tip1: Two pointer for sorted array (#Array 1. Two Sum) Tip2: Sum[i:j] = Sum[0:j] - Sum[0:i] for continuous array (# Array 560. Subarray Sum Equals K) Tip3: Knapsack ...
Problem LeetCode 力扣 Python Go Solution Difficulty Tag 0017 Letter Combinations of a Phone Number Medium 回溯、暴力 0034 Find First and Last Position of Element in Sorted Array Medium 二分 0039 ...
leetcode 2 和 c 问题解决 在这里,您可以通过他们的解决方案找到许多编码问题。 NPTEL 作业中的问题 要找到给定半径值的圆的周长和面积。您应该在程序中使用 Math.PI 常量。如果半径为零或小于零,则打印“请输入非...
leetcode 和 oj otherOnline-Judges 在线评委中的问题,如 codeforce、Spoj、hackerearth 等我在在线评委中尝试过的问题,如 codeforce、SPOJ、hackerearth 力码 1 -Two Sum - 接受 7 - 反向整数 - 接受 9 - 回文数 ...
leetcode双人赛LeetCode 问题分析 本文档总结了 LeetCode 问题的解决方案。 3Sum :首先对数组进行排序,然后创建三个指针 - i指向头部, j指向尾部, k指向枢轴。 if (a[i] + a[k] + a[j]) < 0, i++ else j-- 。...
leetcode 答案力码 API 使用 TypeScript 编写的 Leetcode ..."two-sum" ) ; // Fetch more properties of this problem await problem . detail ( ) ; // Show problem content, test case, code snippet
sum 经典例题: 1. 二维数组查找问题。限制条件为左到右递增,上到下递增。 2. KMP算法实现 UVA problem 100 - The 3n + 1 problem 151 - Power Crisis -> 约瑟夫问题DP 问题 10607 - Joseph's Cousin -> 约瑟夫问题...
Problemset List(GLPL) 说明 为 生成目录导航列表。 形式为: - [ ] 0001.两数之和(Two Sum) :[题目描述](https://leetcode-cn.com/problems/two-sum/),[解答]...
数据库中包含表problem,及字段id(题目编号)、title(题目名称)和slug(题目slug)。例如: id title slug 1 Two Sum two-sum 2 Add Two Numbers add-two-numbers 3 Longest Substring Without Repeating ...
$problem_title ├── solution.hpp # implement the solution └── TEST.cpp # UNIT Testcases 现在。 编写用于测试和解决方案的代码! /* * 1. Two Sum/TEST.cpp * */ # include " ../../framework/header.hpp ...
Problem 95,98(80 already!) 我经常在递归的结束地方忘记return!!! 题型一:经典暴力递归:(里面涉及到重复不重复的时候,需要注意该如何处理!) 模板都是一样的 039:Combination Sum 040:Combination Sum II ...
如果没有找到题目文件夹,则进行创建,命名方式为id.problem_title,比如001.two-sum/。 4. 更新至GitHub 提交之前,先将远程代码更新至本地仓库。 git pull 提交本地代码至远程仓库。 git add . git commit -m ...
leetcode问题(总数:224) 1-50(数量:37) 26从排序的数组中删除重复项.md 27-删除元素.md 28-实现-strstr.md 第29章二分一体.md 3个最长的子字符串,没有重复的字符.md 33.在旋转排序数组中搜索.md 34在...
leetcode-problem-crawler -r 1-5 爬行问题1、2、3: $ npx leetcode-problem-crawler -r 1,2,3 只是爬行问题5: $ npx leetcode-problem-crawler -r 5 然后我们将得到如下目录: ├── 001.two-sum │ ├── ...
sum c LeetCode The problem solving report (C Program) LeetCode 解题报告 C语言实现方式 已经完成的题目列表 工程中有解题报告并且标注了运行时间。 题目标号 题目 1 2 3 7 12 13 14 20 21 26 28 35 38 66 69 100...
Leetcode-Problem-1780__检查数字是否为三的幂之和__Python3 描述 给定一个整数n ,如果可以将n表示为三的幂的和,则返回true。 否则,返回false。 如果存在整数x使得y = 3 ^ x,则整数y是3的幂。 范例1: Input:...
Sum 其他OJ的第一题一般都是A+B Problem,看题目名字 我也以为是那种水水的题目,最后发现并不是那么简单。 最开始直接在网页上面写了一个暴力方法求解的代码, 超时了。后面减小了循环内的运算量才过,不过还是暴力...
problem like LeetCode problems. Question: We have 100 numbers, now need to be divided into 10 groups, and let the sum of each group of figures the smallest difference. Only need to find a set of ...