LeetCode-in-All

15. 3Sum

Medium

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []

Output: []

Example 3:

Input: nums = [0]

Output: []

Constraints:

Solution

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    public function threeSum($nums) {
        sort($nums);
        $len = count($nums);
        $result = [];
        for ($i = 0; $i < $len - 2; $i++) {
            $l = $i + 1;
            $r = $len - 1;
            while ($r > $l) {
                $sum = $nums[$i] + $nums[$l] + $nums[$r];
                if ($sum < 0) {
                    $l++;
                } elseif ($sum > 0) {
                    $r--;
                } else {
                    $list = [$nums[$i], $nums[$l], $nums[$r]];
                    $result[] = $list;
                    while ($l < $r && $nums[$l + 1] == $nums[$l]) {
                        $l++;
                    }
                    while ($r > $l && $nums[$r - 1] == $nums[$r]) {
                        $r--;
                    }
                    $l++;
                    $r--;
                }
            }
            while ($i < $len - 1 && $nums[$i + 1] == $nums[$i]) {
                $i++;
            }
        }
        return $result;
    }
}