Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: The solution set must not contain duplicate quadruplets. For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

        博主的答案最后是TLE,虽然代码正确,但是算法耗时太长,算法复杂度为O(N^4),以下是博主代码:

        是的,博主在写代码时没有考虑算法复杂度的问题,并且对一些技巧不太了解,下面就来解析一个算法复杂度为O(N^3)的代码:

        确实比博主的代码简洁多了,下面介绍其中的一些技巧:

    1.nums在使用前进行排序

★2.通过相邻相等的判断,实现了相同答案的滤除

★3.在降低算法复杂度方面,从一个数组中取出四个数的方法,先从其中取出两个,都是从左向右,后两个数如果也这样取,那就是O(N^4),所以以下代码至关重要:

        注意这个if、else,我们要处理的问题是固定和,如果已经有一个答案了,那么原先的基础上的两个值都要改变,不能只改变一个,如果目前没有答案,那我们只改变其中一个值,直到遇到答案,这里有一个大小相对变化的问题,不用担心漏掉,这样就把算法复杂度降低了一个数量级O(N^3)。

        总体来说,就是将两个数确定下来之后,剩下的是一个定和问题,从而使用低算法复杂度的算法。当然,这份代码效率也并不是很高,还有其它更快的算法比较常见的是使用hash表,还有其它另人瞠目的算法,无奈博主水平有限,以后有机会再介绍吧。

        OK,See You Next Chapter!

发表评论

电子邮件地址不会被公开。 必填项已用*标注