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:
0 <= nums.length <= 3000-105 <= nums[i] <= 105
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;
}
}