面试题：找出所有和为零的不重复三元组

之前在南山软件产业园靠近腾讯那边面试了一家公司，其中有一道算法题挺有印象的。当时没能准确写出答案，后来去网上找了下资料将答案记录了下来，题目如下：

一个包含n个整数的数组S，判断S中是否存在元素a + b + c = 0，查找数组中所有和为零的三元组。
注意：解决方案集不能包含重复的三元组。

例如，数组S = [-1,0,1,2,-1,-4]
答案是：

[
   [-1 , 0 , 1],
   [-1 , -1 , 2]
]

解题思路：
· 首先对数组进行排序，时间复杂度为O(n*logn)
· 然后对数组进行两层的遍历，先取出当前遍历的数字为nums[i]，然后从数组两侧取出数字分别为nums[begin]和nums[end]，然后三个数求和值为sum
· sum === 0，将三个数加入结果之中，同时将两侧的下标向中间移动，直到不与之前取出的数字相同，避免出现重复的三元组
· sum > 0，因为数组有序，说明右侧的数字过大，所以下标左移，故而执行end--
· sum < 0，因为数组有序，说明左侧的数字过小，所以下标右移，所以执行begin++
· 因为两层的遍历时间复杂度为O(n^2)，O(n*logn) + O(n^2) = O(n^2)，所以总体时间复杂度为O(n^2)

代码：

class Solution
{
    /**
     * 获取结果集
     * @param array $nums
     * @return array
     */
    public function getNumList(array $nums = []) : array
    {
        $list = [];
        if (empty($nums) || count($nums) < 3) return $list;
        // 首先进行数组升序排列
        sort($nums);

        for ($i = 0; $i < count($nums); $i++) {
            // 如果第一个数字大于0，则其之后的数字一定大于0(因为已经排序了)，所以三数之和一定大于0，结束循环
            if ($nums[$i] > 0) break;
            // 对三个数中的第一个数字去重
            if ($i > 0 && $nums[$i] === $nums[$i - 1]) continue;
            // 开始查找的下标地址
            $begin = $i + 1;
            // 结束查找的下标地址
            $end  = count($nums) - 1;
            // 当开始查找的下标地址在结束查找的下标地址前边的时候，遍历所有情况
            while ($begin < $end) {
                // 对三个数中的第二个数去重
                while ($begin < $end && $nums[$begin] === $nums[$begin + 1]) $begin++;
                // 对三个数中的第三个数去重
                while ($begin < $end && $nums[$end] === $nums[$end - 1]) $end--;
                $sum = $nums[$i] + $nums[$begin] + $nums[$end];

                if ($sum === 0) {
                    $list[] = [$nums[$i], $nums[$begin], $nums[$end]];
                    //当sum===0时，第一个数保持不变的情况下，第二和第三个数不能再重复了，所以左边的begin向后继续遍历，右边的end向前继续遍历
                    $begin++;
                    $end--;
                } else if ($sum < 0) {
                    // 当sum<0说明左边的数num[begin]太小了，所以要左边的地址+1继续向后遍历
                    $begin++;
                } else if ($sum > 0) {
                    // 当sum>0说明右边的数num[end]太大了，所以要右边的地址-1继续向前遍历
                    $end--;
                }
            }
        }

        return $list;
    }
}

最后写上调试程序：

$nums = [-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6];
$solution = new Solution();
$list = $solution->getNumList($nums);
echo '<pre>';
print_r($list);
echo '</pre>';

结果无误。