Appearance
15. 3Sum
https://leetcode.com/problems/3sum/
c++
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
for (int i = 0; i < nums.size(); i++) {
if (i >= 1 && nums[i] == nums[i-1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.push_back({nums[i], nums[left], nums[right]});
}
if (sum <= 0) {
left++;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
}
if (sum >= 0) {
right--;
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
}
}
}
return result;
}
};
go
func threeSum(nums []int) [][]int {
var result [][]int
sort.Ints(nums)
for i := 0; i < len(nums); i++ {
if i >= 1 && nums[i] == nums[i-1] {
continue
}
left := i + 1
right := len(nums) - 1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum == 0 {
result = append(result, []int{nums[i], nums[left], nums[right]})
}
if sum <= 0 {
left++
for left < right && nums[left] == nums[left-1] {
left++
}
}
if sum >= 0 {
right--
for left < right && nums[right] == nums[right+1] {
right--
}
}
}
}
return result
}
js
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
nums.sort((a, b) => a - b)
var result = []
for (let i = 0; i < nums.length; i++) {
if (i >= 1 && nums[i] === nums[i - 1]) {
continue
}
let left = i + 1
let right = nums.length - 1
while (left < right) {
let sum = nums[left] + nums[right] + nums[i]
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]])
}
if (sum <= 0) {
left++
while (left < right && nums[left] === nums[left - 1]) {
left++
}
}
if (sum >= 0) {
right--
while (left < right && nums[right] === nums[right + 1]) {
right--
}
}
}
}
return result
}
py
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
result = []
for i in range(len(nums) - 2):
if i >= 1 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
if s <= 0:
left += 1
while left < right and nums[left] == nums[left - 1]:
left += 1
if s >= 0:
right -= 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
return result