Javascript的那个3重循环,明显很久没做算法题了,就先不说了;
伪代码那个是错的啊,有这么几个地方:
1. if (r < j) continue; //这句是错的,应该是 if (r <= j),否则我给你一个[-2, 1, 2] 你会给我输出一个 [-2, 1, 1]。
2. 查重仍然不够。即使把(1)的错误改掉,仍然会有错,比如有 [-2, 1, 1, 1],这个伪代码会把 [-2, 1, 1]输出两次,而题目要求是 unique triplet。
另外,用hashtable显然比binarysearch时间复杂度低,伪代码的复杂度是O(n^2 log(n)),如果用hash就是O(n^2)。
当然复杂度的问题并不太大,你如果额外说只能用O(1)的空间那我也接受。但是 edge case 不考虑好,就是不及格啊,尤其是上来就声称“这题我见过,知道怎么做”的情况下,写成这样真是挺糟糕的。
首先,题目:
3Sum | LeetCode OJ节目中答应了大家要放出
@winter和
@赵劼写的代码。
下面两张是二位分析 winter 代码的分析过程,实在看不懂了……
限于节目的时长,我们没有把整个的创作过程、review 过程及评价过程放出来。要是感兴趣的人多,我们找机会再把这个部分的完整版视频放出来?
更新:完整版来了,请戳→
《职人介绍所》第 21 期:你们要的 winter 赵劼徒手写码到分析代码完整版真可怜,被要求手写代码,还不能掀桌子。
============================================
正经答题好了。
先讲这个算法题好了。
其实从题目来讲,这个题目太难了,而且过分侧重于底层的算法而不是高层的结构。
leetcode的题很多时候其实是一种基本功的训练,简单说这个题目就像是请两个数学教授来解一个大型的不定积分,并不能体现出超乎常人的能力出来。
这种题目要面试的时候手写真的是要掀桌子的。而且从答案来看,老赵确实占便宜了。像这种算法题,最麻烦的是你要知道坑在哪里,而你没做过的话就很难搞清楚。
老赵上来直接排序然后两重循环+BinarySearch,就是因为他知道这条简单直接的路是没有坑的,winter没见过吃亏了。至于排重的问题, HashSet的时间复杂度是O(n)(创建O(n),查询O(1),总体O(n)),也就是不会增加时间复杂度,除非你其他部分的时间复杂度做到了O(n)这个程度了(当然复杂度不代表最终的时间)。
那个Hash很明显是指HashSet应该可以代替BinarySearch提升性能嘛。
最后讲点别的。
很多时候最佳方案不是最好的方案,如果面试遇到这种问题,在没有限定复杂度的情况下,三重循环+结果排重是最稳妥的实现,稍微优化一下就可以得到老赵的代码。先做出来再去优化,比做不出来要好很多。
写了个风骚的版本,也通过leetcode了。。。。。
public class Solution { public IList<IList<int>> ThreeSum( int[] nums ) { var all = new HashSet<int>( nums ); var left = new HashSet<int>(); var right = new HashSet<int>(); var doubles = new HashSet<int>(); var zeros = 0; if ( nums.Length < 3 ) return new int[][] { }; foreach ( var i in nums ) { if ( i < 0 ) { if ( left.Add( i ) == false ) doubles.Add( i ); } else { if ( right.Add( i ) == false ) doubles.Add( i ); if ( i == 0 ) zeros++; } } var result = from i in left from j in right let k = -(i + j) where all.Contains( k ) && (k != i || doubles.Contains( i )) && (k != j || doubles.Contains( j ))//这里是避免只出现一次的数字被两次添加到结果 select k > j ? new { i, j, k } : k > i ? new { i, j = k, k = j } : new { i = k, j = i, k = j };//这里是排序,为后面的排重做准备 var _result = result.Distinct().Select( item => new[] { item.i, item.j, item.k } ).ToList(); if ( zeros >= 3 ) _result.Add( new[] { 0, 0, 0 } );//这里是000补丁 return _result.ToArray(); } }
其实我主要是想测试一下leetcode对LINQ Expression的支持程度。
算法很简单,就是把正负数配对,然后看他们的和的取反是不是存在,存在就说明这是一个合法的结果。
其实相当暴力,但关键在于正负数配对,导致性能可以很大提升。
因为三个数之和要等于零,必然是++-、--+和000(我们把0归到+或-之一)这三种情况中的一种。
顺便说一句这个纯属卖弄风骚的代码版本,竟然是C#里面跑最快的?突然很奇怪其他人都写了些啥?!(╯°Д°)╯ ┻━┻
想了想,如果是我的话,我会有三个反应。
1,事先告知不要问我狗屎题
2,如果非要问狗屎题,那么必须提前一个月告诉我,不然我不好准备
3,如果观众喜欢狗屎,那么就准备一坨更大的狗屎,让观众满意
请了老赵和 winter,结果拖住别人做这种狗屎题……
难道不应该问一点编程的心法,设计的思想,人生的经验吗
还是说知乎的这个节目只想面向知乎的核心用户群……