15. Triplet sum
#include <stdlib.h>
static int cmp(const void *a, const void *b) {
return *(const int *)a - *(const int *)b;
}
int **threeSum(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {
qsort(nums, numsSize, sizeof(int), cmp);
int capacity = 16;
int **result = malloc(capacity * sizeof(int *));
*returnColumnSizes = malloc(capacity * sizeof(int));
*returnSize = 0;
for (int idx = 0; idx < numsSize; idx++) {
if (idx > 0 && nums[idx] == nums[idx - 1]) {
continue;
}
int left = idx + 1, right = numsSize - 1;
while (left < right) {
int total = nums[idx] + nums[left] + nums[right];
if (total == 0) {
if (*returnSize == capacity) {
capacity *= 2;
result = realloc(result, capacity * sizeof(int *));
*returnColumnSizes = realloc(*returnColumnSizes, capacity * sizeof(int));
}
int *triplet = malloc(3 * sizeof(int));
triplet[0] = nums[idx];
triplet[1] = nums[left];
triplet[2] = nums[right];
result[*returnSize] = triplet;
(*returnColumnSizes)[*returnSize] = 3;
(*returnSize)++;
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (total > 0) {
right--;
} else {
left++;
}
}
}
return result;
}15_deduplicaton_checks.cpp
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int> &nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int idx = 0; idx < nums.size(); idx++) {
if (idx > 0 && nums[idx] == nums[idx - 1])
continue; // skip duplicate fixed value
int i = idx + 1, j = nums.size() - 1;
while (i < j) {
int sum = nums[idx] + nums[i] + nums[j];
if (sum == 0) {
result.push_back({nums[idx], nums[i], nums[j]});
i++;
j--;
while (i < j && nums[i] == nums[i - 1])
i++; // skip duplicate left values
while (i < j && nums[j] == nums[j + 1])
j--; // skip duplicate right values
} else if (sum > 0) {
j--;
} else {
i++;
}
}
}
return result;
}
};15_set_of_vectors.cpp
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int> &nums) {
set<vector<int>> triplets;
sort(nums.begin(), nums.end());
for (int idx = 0; idx < nums.size(); idx++) {
int i = idx + 1, j = nums.size() - 1;
while (i < j) {
int sum = nums[idx] + nums[i] + nums[j];
if (sum == 0) {
triplets.insert({nums[idx], nums[i], nums[j]});
i++;
j--;
}
if (sum > 0)
j--;
if (sum < 0)
i++;
}
}
return vector<vector<int>>(triplets.begin(), triplets.end());
}
};package main
import "sort"
func threeSum(nums []int) [][]int {
sort.Ints(nums)
result := [][]int{}
for idx := 0; idx < len(nums); idx++ {
if idx > 0 && nums[idx] == nums[idx-1] {
continue
}
left, right := idx+1, len(nums)-1
for left < right {
total := nums[idx] + nums[left] + nums[right]
if total == 0 {
result = append(result, []int{nums[idx], nums[left], nums[right]})
left++
right--
for left < right && nums[left] == nums[left-1] {
left++
}
for left < right && nums[right] == nums[right+1] {
right--
}
} else if total > 0 {
right--
} else {
left++
}
}
}
return result
}import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int idx = 0; idx < nums.length; idx++) {
if (idx > 0 && nums[idx] == nums[idx - 1]) {
continue;
}
int left = idx + 1, right = nums.length - 1;
while (left < right) {
int total = nums[idx] + nums[left] + nums[right];
if (total == 0) {
result.add(Arrays.asList(nums[idx], nums[left], nums[right]));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (total > 0) {
right--;
} else {
left++;
}
}
}
return result;
}
}class Solution {
threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let idx = 0; idx < nums.length; idx++) {
if (idx > 0 && nums[idx] === nums[idx - 1]) continue;
let left = idx + 1;
let right = nums.length - 1;
while (left < right) {
const total = nums[idx] + nums[left] + nums[right];
if (total === 0) {
result.push([nums[idx], nums[left], nums[right]]);
left++;
right--;
while (left < right && nums[left] === nums[left - 1]) left++;
while (left < right && nums[right] === nums[right + 1]) right--;
} else if (total > 0) {
right--;
} else {
left++;
}
}
}
return result;
}
}class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
nums.sort()
result = []
for idx in range(len(nums)):
if idx > 0 and nums[idx] == nums[idx - 1]:
continue
left, right = idx + 1, len(nums) - 1
while left < right:
total = nums[idx] + nums[left] + nums[right]
if total == 0:
result.append([nums[idx], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif total > 0:
right -= 1
else:
left += 1
return resultstruct Solution;
impl Solution {
fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
nums.sort();
let mut result = Vec::new();
let n = nums.len();
for idx in 0..n {
if idx > 0 && nums[idx] == nums[idx - 1] {
continue;
}
let mut left = idx + 1;
let mut right = n - 1;
while left < right {
let total = nums[idx] + nums[left] + nums[right];
if total == 0 {
result.push(vec![nums[idx], nums[left], nums[right]]);
left += 1;
right -= 1;
while left < right && nums[left] == nums[left - 1] {
left += 1;
}
while left < right && nums[right] == nums[right + 1] {
right -= 1;
}
} else if total > 0 {
right -= 1;
} else {
left += 1;
}
}
}
result
}
}