15. 三数之和

题意：

解题思路：

思路：
    1. 首先对 nums 进行从小到大排序；
    2. 枚举第一个数字，然后采用两头夹逼的方式，无重复的寻找剩下的两个数字；
        2.1 初始化left = $i + 1, right = count($num) - 1;
        2.2 当left < right 时，如果nums[left] + nums[right] = target, 则增加一组答案，同时left, right 左右移动，否则根据 nums[left] + nums[right] 与 target的大小关系，进行左右移动;

时间复杂度
    1. 排序的时间复杂度为O(nlog⁡n)；
    2. 第一层for情况执行n次，每次内部会遍历 i + 1后面的数字一次，最后情况O(n2)

PHP代码实现：

class Solution {
    function threeSum($nums) {
        if (!$nums) return [];
        sort($nums);
        $ret = [];
        for ($i = 0; $i < count($nums) - 2; $i++) {
            if ($i > 0 && $nums[$i] == $nums[$i - 1]) continue;
            $left = $i + 1;
            $right = count($nums) - 1;
            $needNum = 0 - $nums[$i];
            while ($left < $right) {
                if ($nums[$left] + $nums[$right] == $needNum) {
                    array_push($ret, [$nums[$i], $nums[$left], $nums[$right]]);
                    while ($left < $right && $nums[$left] == $nums[$left + 1]) $left ++;
                    while ($left < $right && $nums[$right] == $nums[$right - 1]) $right --;
                    $left ++; $right --;
                } else if ($nums[$left] + $nums[$right] > $needNum) {
                    $right--;
                } else $left ++;
            }
        }
        return $ret;
    }
}

GO代码实现：

func threeSum(nums []int) [][]int {
    var res [][]int
    sort.Ints(nums)
    fmt.Printf("%v\n", nums)
    for i := 0; i < len(nums); i++ {
        var left = i + 1
        var right = len(nums) - 1
        if i > 0 && nums[i] == nums[i - 1] {
            continue
        }
        for left < right {
            var sum = nums[i] + nums[left] + nums[right]
            if sum == 0 {
                res = append(res, []int{nums[i], nums[left], nums[right]})
                for left < right && nums[left] == nums[left + 1] {
                    left++
                }
                for left < right && nums[right] == nums[right - 1] {
                    right--
                }
                left++
                right--
            } else if sum > 0 {
                right--
            } else {
                left++
            }
        }
    }
    return res
}