实现思路

说四数之和之前，还是先说一下三数之和，对理解四数之和有帮助。

三数之和可以用暴力解法，使用三重循环，时间复杂度为O(n^3)。

四数之和也可以用暴力解法，使用四重循环，时间复杂度为O(n^4)。

上面的解法时间复杂度太高，执行起来有可能超时。所以需要另外的解法。

判断三数之和时，我们首先把待判断的数组进行排序，是为了减少三元组的判断。然后以遍历的每一个元素的基准，由于数组是有序的，以当前元素后的首尾元素向中间移动，组合之外的两个元素进行判断。

我们知道了三数之和的解法，那么四数之和的解法就简单了，我们只需要在三数之和的解法外面再重新加一个循环就可以实现四数之和。只不过有一些边界问题需要处理。

四数之和判断的是是否等于变量$target，$target的值不固定。

完整代码

第563-566行代码，如果数组长度小于 4，则返回空数组，因为数组内没有符合条件的四元组。

第567行代码，使用PHP内置函数对数组进行升序排序。

第568行代码，定义一个数组，存储符合条件的四元组。

第569-602行代码，遍历数组，寻找符合条件的四元组。

第569行代码，此为第一重循环，即当前遍历元素一定时，组合其它的三个元素。遍历的下标最大值小于等于数组长度减3，因为第一重循环遍历到倒数第4个元素时，后面只有三个元素，再继续遍历没有意义。

第570-572行代码，翦枝操作，避免重复的四元组，当前遍历元素如果等于上一个元素的话，由于上一个元素已经组合过其它元素，所以当前元素为了避免重复，需要跳过，继续遍历下一个元素。

第574行代码，此为第二重循环，即第一重循环的元素一定时，当前循环遍历的元素也一定时，组合其它的两个元素。遍历的下标最大值小于等于数组长度减2，因为第二重循环遍历到倒数第3个元素时，后面只有两个元素，再继续遍历没有意义。

第575-577行代码，翦枝操作，避免重复的四元组，当前遍历元素如果等于上一个元素的话，由于上一个元素已经组合过其它元素，所以当前元素为了避免重复，需要跳过，继续遍历下一个元素。

第579-580行代码，定义两个移动的指针，$left指针初始位置为第二重循环位置加1，$right指针位置为数组长度减1。

第581行代码，不断移动两个指针位置，如果$left位置大于等于$right位置就退出循环，说明此时有元素重复。

第582-583行代码，由于在PHP中有符号INT的最大值为21亿多，而题目中数组中的值最大为10亿，如果四个元素都为10亿，就会超出INT的最大值。所以我们需要通过两个数相加做对比。

$sumOne的值为两个指针位置的元素值相加，$sumTwo的值为目标值减去前两重循环位置的元素值相加，为什么需要目标值相减呢？因为目标值有可能为0，那么两两相加做比较的话，有可能出现相反数。不能等值比较。

第585-594行代码，两个值相等，则把四个元素的值放入定义的$arr数组内，然后判断$left指针位置的下一个元素是否相等，若相等则$left指针增加1。$right指针同$left。最后把$left指针加1，$right指针减1。继续判断后面的元素。

第595-596行代码，如果相减后的数值大于两个指针相加的数值，那么$left指针位置加1。因为由于前两重循环的位置固定，所以目标值与其相减后的值也固定。两个指针位置的元素值就需要增大，所以需要$left指针位置加1继续判断。

第597-598行代码，如果如果相减后的数值小于两个指针相加的数值，那么$right指针位置减1，

第603行代码，返回符合条件的四元组。

本文转载自: 掘金