源题目

https://leetcode-cn.com/problems/3sum/

15. 三数之和

难度中等3639
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 _a + b + c = _0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = [] 输出：[]
示例 3：
输入：nums = [0] 输出：[]

提示：

• 0 <= nums.length <= 3000

• -105 <= nums[i] <= 105

  class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function threeSum($nums) {
        $len = count($nums);
        if(!$nums || $len <3) return [];
        $ret = [];
        sort($nums);
        for($i =0; $i < $len; $i++){
            if($nums[$i] > 0) continue;
            if($i > 0 && $nums[$i-1] == $nums[$i]) continue;
            $left = $i + 1;
            $right = $len -1;
            while($left < $right){
                $sum = $nums[$i] + $nums[$left] + $nums[$right];
                if($sum == 0){
                    $ret[] = [$nums[$i] , $nums[$left] , $nums[$right]];
                    while($left < $right && $nums[$left] == $nums[$left + 1]) $left ++;
                    while($left < $right && $nums[$right -1] == $num[$right]) $right --;
                    $left ++;
                    $right --;
                }else if($sum > 0){
                    $right --;
                }else{
                    $left ++;
                }
            }
        }
        return $ret;
    }
  }