当前位置 博文首页 > 前端开发博客:一个算法面试题的5种不同解法
点击下方“前端开发博客”关注公众号
回复“2”加入前端群
在[3 2 1 2 3 4 5]这个数组中,和为10的子数组是[1 2 3 4],所以答案应该是[2,5]。
和为15的子数组是[1 2 3 4 5],答案为[2,6]。
这是一道非常有意思的题,为什么这么说?最简单的解法只要具备基本的编程知识就能写出,更优的解法需要你有数据结构和算法能力,越高效的解法越巧妙,可能你一下子无法想出所有的解法,但我相信你看完这篇博客一定会感叹算法的神奇。
回到这道题上来,实际上它有着O(n^3)
?、O(n^2)
?、O(nlogn)
?、O(n)?
4种时间复杂度的解法,如果算上空间复杂度的差异的话总共5种解法,我觉得还是比较能考察到一个人的算法水平的。接下来让我带领大家由简入难看下从青铜到王者的5种解法,带大家吊打面试官。
这里我们设输入参数为(arr[],target),后续代码中我会用s和e来分别表示起始和终止位置。另外为了简化代码思路,我们假设给定的参数里最多只有一个解(实际上多个解也不难,但会让代码变长,不利于描述思路,多解的情况就留给你当课后作业了)。
首先当然是最简单的暴力求解了,遍历起始位置s和结束位置e,然后求s和e之间所有数字的和。三层循环简单粗暴,不需要任何的技巧,相信你大一刚学会编程就能解出来。
public?int[]?find(int[]?arr,?int?target)?{
????????for?(int?s?=?0;?s?<?arr.length;?s++)?{
????????????for?(int?e?=?s+1;?e?<?arr.length;?e++)?{
????????????????int?sum?=?0;
????????????????for?(int?k?=?s;?k?<=?e;?k++)?{?//?求s到e之间的和
????????????????????sum?+=?arr[k];
????????????????}
????????????????if?(target?==?sum)?{
????????????????????return?new?int[]{s,?e};
????????????????}
????????????}
????????}
????????return?null;
????}
我们来分析下时间复杂度,很明显是O(n^3),当n超过1000时就会出现肉眼可见的慢,想想如何优化?
上面代码中,我们每次都需要算从s到e之间的数组的和sum[s,e],假设我之前已经求过了[1,10]之间的和sum[1,10],现在要求[2,10]之间的和sum[2,10],显然这中间有很大一部分是重叠的(sum[2,10]),能不能把这部分重复扫描给消除掉?这里就需要做下巧妙的变换了。
实际上sum[s, e] = sum[0, e] - sum[0, s-1]
, sum[0,i]我们可以预先保存下来,然后重复使用。实际上sum数组我们可以通过一遍数据预处理获取到。上图中,arr蓝色区域的和正好等于sum数组中红色减去绿色,即sum(arr[3]-arr[7]) = sum[7]-sum[2]
。
回到代码上来,编码实现中我用了额外一个数组arrSum来存储0到i(0<=i<n)之间所有的和,为了处理方便sumArr下标从1开始,sumArr[i]表示远数组中sum[0, i-1]。有了sumArr之后,sum[s,e]就可以通过sumArr[e+1]-sumArr[s]间接获取到。完整代码如下:
?public?int[]?find(int[]?arr,?int?target)?{
????????int[]?sumArr?=?new?int[arr.length?+?1];
????????for?(int?i?=?1;?i?<?sumArr.length;?i++)?{
????????????sumArr[i]?=?sumArr[i-1]?+?arr[i-1];??//?预处理,获取累计数组
????????}
????????for?(int?s?=?0;?s?<?arr.length;?s++)?{
????????????for?(int?e?=?s+1;?e?<?arr.length;?e++)?{
????????????????if?(target?==?sumArr[e+1]?-?sumArr[s])?{
????????????????????return?new?int[]{s,?e};
????????????????}
????????????}
????????}
????????return?null;
????}
通过上述用空间换时间的方式,我们可以直接将时间复杂度从O(n^3)
?降低到O(n^2)
。
细心的你可能已经发现了,因为给出的arr都是正整数,所以sumArr一定是递增且有序的,对于有序的数组,我们可以直接采用二分查找。对于这道题而已,我们可以遍历起点s,然在sumArr中二分去查找是否有终点e,如果s对于的e存在,那么sumArr[e]一定等于sumArr[s] + target,改造后的代码如下,相比于上面代码,增加了二分查找。
public?int[]?find(int[]?arr,?int?target)?{
????????int[]?sumArr?=?new?int[arr.length?+?1];
????????for?(int?i?=?1;?i?<?sumArr.length;?i++)?{
????????????sumArr[i]?=?sumArr[i-1]?+?arr[i-1];
????????}
????????for?(int?s?=?0;?s?<?arr.length;?s++)?{
????????????int?e?=?bSearch(sumArr,?sumArr[s]?+?target);
????????????if?(e?!=?-1)?{
????????????????return?new?int[]{s,?e};
????????????}
????????}
????????return?null;
????}
????//?二分查找?
????int?bSearch(int[]?arr,?int?target)?{?
????????int?l?=?1,?r?=?arr.length-1;
????????while?(l?<?r)?{
????????????int?mid?=?(l?+?r)?>>?1;
????????????if?(arr[mid]?>=?target)?{
????????????????r?=?mid;
????????????}?else?{
????????????????l?=?mid?+?1;
????????????}
????????}
????????if?(arr[l]?!=?target)?{
????????????return?-1;
????????}
????????return?l?-?1;
????}
由此,我们又继续将时间复杂从O(n^2)降低到了O(nlogn)。
有序数组的查找除了可以用二分优化,还可以用hashMap来优化,借助HashMap O(1)的查询时间复杂度。我们又一次用空间来换取了时间。
public?int[]?find(int[]?arr,?int?target)?{
????????int[]?sumArr?=?new?int[arr.length?+?1];
????????Map<Integer,?Integer>?map?=?new?HashMap<>();
????????for?(int?i?=?1;?i?<?sumArr.length;?i++)?{
????????????sumArr[i]?=?sumArr[i-1]?+?arr[i-1];
????????????map.put(sumArr[i],?i-1);
????????}
????????for?(int?s?=?0;?s?<?arr.length;?s++)?{
????????????int?e?=?map.getOrDefault(sumArr[s]+target,?-1);
????????????if?(e?!=?-1)?{
????????????????return?new?int[]{s,?e};
????????????}
????????}
????????return?null;
????}
我们终于将时间复杂度降低到了O(n),这可是质的飞跃。
别急,还没结束,对于这道题还有王者解法。上文中我们通过不断的优化,将时间复杂度从O(n^3)一步步降低到了,但我们却一步步增加了存储的使用,从开始新增的sumArr数字,到最后的又增加的HashMap,空间复杂度从O(1)变为了O(n)。有没有办法把空间复杂度也给将下来?我能写到这那必然是有的。
这种算法叫做尺取法。尺取法,这个名字有点难理解。我们直接举个具体的例子,假设有n调长度不一的绳子并列放在一起,你需要找出其中连续的一部分绳子组成一条长度为target的绳子,这里需要注意是连续。这时候你可以找一个长度为target的尺子,然后把绳子一段段往尺子上放,如果发现短了就往后面再接一根,如果发现长了,就把最头上的一根扔掉,直到长度恰好合适。
在使用中我们并不需要这把尺子,只需要拿target作为标尺即可。说起来可能比较难理解,直接举个例子,下图演示了从数组中找到和为22的子数组的过程。
只要小了就右加,大了就左减,直到找到目标。
为什么尺取法是对的?我理解尺取法其实是解法二白银解法的一种优化,也是遍历了起点s,但是对终点e不做无效的遍历,如果e到某个位置后已经超了,因为数组里都是正数,再往后肯定是超的,也就没必要继续遍历e了。转而去调整s,如果s右移到某个位置后总和小了,s再往右总和只会更小,也就没必要继续调整s了…… 整个过程就像是先固定s去遍历e,然后固定e再去遍历s ……,直到得到结果。
尺取法可用的基础在于e往右移动总和一定是增的,s往右移总和一定是减的,也就是说数组中所有的数必须是正的。?没有完美的算法可以解决任何问题,但对于特定的问题一定有最完美的解法。
说完尺取法,我们来看下用尺取法是如何解决这道题的,代码比较简单,如下:
?public?int[]?find(int[]?arr,?int?target)?{
????????int?s?=?0,?e?=?0;
????????int?sum?=?arr[0];
????????while?(e?<?arr.length)?{
????????????if?(sum?>?target)?{
????????????????sum?-=?arr[s++];
????????????}?else?if?(sum?<?target)?{
????????????????sum?+=?arr[++e];
????????????}?else?{
????????????????return?new?int[]{s,?e};
????????????}
????????}
????????return?null;
????}
只有一层循环,时间复杂度O(n)。没有额外的空间占用,空间复杂度O(1),这就是最完美的解法。
这道算法题乍看简单,细看其实真的不简单。可能你面试遇到,没办法一下子想到最优的解,但给出一个可行的解总比没有解强。我之前面试问别人这个题,他一上来就是想着怎么最优解决,反而连最简单的青铜解法都没写出来。记得下次面试,实在是解不出来就先给个60分的答案,然后再想办法把分数提升上去,别最后交了白卷。?给出一个可行解,然后再持续迭代优化,我觉得这也是解决一个复杂问题比较好的思路。
最后送大家一句鸡汤,没有人生下来就是王者,只是不断的努力成为了王者罢了。
推荐阅读??点击标题可跳转
JavaScript洗牌算法之重复抽奖(附送书的抽奖结果)
动图展示前端10大经典算法
JavaScript中的算法(附10道面试常见算法题解决方法和思路)
关注下方「前端开发博客」,回复?“加群”
加入我们一起学习,天天进步
如果觉得这篇文章还不错,来个【分享、点赞、在看】三连吧,让更多的人也看到~
???“分享、点赞、在看” 支持一波??