TreeSum

题目：https://leetcode.com/problems/3sum/
two sum的升级版，注意一个组合只能出现一次

1.数组排序
2.找到一个数字后，立马对后面的数字进行查找，使得后面两数之和为前面数字的相反数，（两个指针往中间找）
3.由于一个组合只能出现一次，所以，当发现有相同数字的时候跳过

<?php


class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     * @brief https://leetcode.com/problems/3sum/
     */
    function threeSum($nums) {
        $res = [];
        sort($nums);
        for ($i = 0; $i < count($nums); $i++) {
            if ($nums[$i] > 0) {
                break;
            }

            if ($i > 0 && $nums[$i] == $nums[$i - 1]) {
                continue;
            }

            $target = 0 - $nums[$i];
            $m      = $i + 1;
            $n      = count($nums) - 1;
            while ($m < $n) {
                if ($nums[$m] + $nums[$n] == $target) {
                    $res[] = [$nums[$i], $nums[$m], $nums[$n]];
                    while ($m < $n && $nums[$m] == $nums[$m + 1]) {
                        $m++;
                    }
                    while ($m < $n && $nums[$n] == $nums[$n - 1]) {
                        $n--;
                    }
                    $m++;
                    $n--;
                } else if ($nums[$m] + $nums[$n] < $target) {
                    $m++;
                } else {
                    $n--;
                }
            }

        }
        return $res;
    }
}

$so   = new Solution();
$nums = [-1, 0, 1, 2, -1, -4];
$a    = $so->threeSum($nums);
var_dump($a);