3Sum in Python
3 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.
Try every combination of positions i < j < k. When the three values sum to 0, sort them into a tuple and add it to a set, which drops triplets you have already found. Sorting each triplet before storing it is what lets the set catch a second (-5, 2, 3) built from a different 2. Apart from the answer it needs no memory, but it checks every group of three positions.
def three_sum(nums: list[int]) -> list[list[int]]:
found: set[tuple[int, ...]] = set()
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if nums[i] + nums[j] + nums[k] == 0:
found.add(tuple(sorted((nums[i], nums[j], nums[k]))))
return [list(t) for t in sorted(found)]
Fix the first position i and the problem becomes Two Sum on the rest of the list: find two numbers that add up to -nums[i]. Walk j to the right and keep a set of the values you have passed since i. If the number that completes the triplet is in the set, record it. Checking need in seen before adding nums[j] keeps every position used once. Set lookups take constant time on average, so the innermost loop disappears; it still needs the set of sorted tuples to remove repeats.
def three_sum(nums: list[int]) -> list[list[int]]:
found: set[tuple[int, ...]] = set()
for i in range(len(nums)):
seen: set[int] = set() # values between position i and position j
for j in range(i + 1, len(nums)):
need = -nums[i] - nums[j]
if need in seen:
found.add(tuple(sorted((nums[i], need, nums[j]))))
seen.add(nums[j])
return [list(t) for t in sorted(found)]
Sort the list first. For each first value nums[i], put lo just after it and hi at the end. If the sum is too small, only moving lo right can raise it; if it is too big, only moving hi left can lower it. On a match, record it and move both. Equal values now sit side by side, so repeats are skipped with one comparison to the neighbour, and no set is needed. The sort costs O(n log n) and the loops O(n²); besides the output and the sort itself, nothing grows with n. nums.sort() changes the caller's list, so pass nums[:] if you need the original order.
def three_sum(nums: list[int]) -> list[list[int]]:
nums.sort() # sorts the caller's list in place
result: list[list[int]] = []
for i in range(len(nums) - 2):
if nums[i] > 0:
break # three positive numbers can't sum to 0
if i > 0 and nums[i] == nums[i - 1]:
continue # same first value, same triplets
lo, hi = i + 1, len(nums) - 1
while lo < hi:
total = nums[i] + nums[lo] + nums[hi]
if total < 0:
lo += 1
elif total > 0:
hi -= 1
else:
result.append([nums[i], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1 # skip repeats of the middle value
return result
3Sum in JavaScript
3 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.
Three for loops pick indexes i < j < k, so each group of positions is tried once. A hit is sorted numerically and stored in a Map under a string key such as "-3,-2,5". The key is what removes repeats: two arrays with the same contents are still different objects, and a Set of arrays would keep both. A second 2 produces the key "-5,2,3" again, so found.set simply overwrites the first entry. At the end the stored triplets are sorted with a two-level comparator so the output is easy to read.
function threeSum(nums) {
const found = new Map(); // "a,b,c" -> [a, b, c]
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
for (let k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] === 0) {
const triplet = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
found.set(triplet.join(','), triplet);
}
}
}
}
return [...found.values()].sort((x, y) => x[0] - y[0] || x[1] - y[1]);
}
Once nums[i] is fixed, the remaining job is a pair search: the two other values must add up to -nums[i]. While j moves right, a fresh Set remembers every value it has stepped over since i, and seen.has(need) answers in constant time on average. That replaces the third loop. Calling has before add is what stops an element from pairing with itself. The 0 - in need is deliberate: with -nums[i] - nums[j] the zeros case gives [ 0, -0, 0 ]. Repeats are still possible, so the same string-keyed Map and final sort stay.
function threeSum(nums) {
const found = new Map(); // "a,b,c" -> [a, b, c]
for (let i = 0; i < nums.length; i++) {
const seen = new Set(); // values strictly between i and j
for (let j = i + 1; j < nums.length; j++) {
const need = 0 - nums[i] - nums[j]; // not -nums[i]: that turns 0 into -0
if (seen.has(need)) {
const triplet = [nums[i], need, nums[j]].sort((a, b) => a - b);
found.set(triplet.join(','), triplet);
}
seen.add(nums[j]);
}
}
return [...found.values()].sort((x, y) => x[0] - y[0] || x[1] - y[1]);
}
Sorting with (a, b) => a - b puts the numbers in true numeric order, which makes the sum predictable. For each anchor nums[i], lo starts right after it and hi at the last index. A negative sum means lo must step right, a positive one means hi must step left, and zero is a triplet to push before moving both. Because equal numbers are now neighbours, a single === against the previous element skips duplicates, so neither a Set nor a Map is needed. Time is O(n log n) for the sort plus O(n²) for the loops; the cost of the O(1) extra space is that nums.sort reorders the caller's array.
function threeSum(nums) {
nums.sort((a, b) => a - b); // numeric order, in place
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) break; // everything from here on is positive
if (i > 0 && nums[i] === nums[i - 1]) continue; // repeated first value
let lo = i + 1;
let hi = nums.length - 1;
while (lo < hi) {
const sum = nums[i] + nums[lo] + nums[hi];
if (sum < 0) {
lo++;
} else if (sum > 0) {
hi--;
} else {
result.push([nums[i], nums[lo], nums[hi]]);
lo++;
hi--;
while (lo < hi && nums[lo] === nums[lo - 1]) lo++; // repeated middle value
}
}
}
return result;
}
3Sum in TypeScript
3 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.
Three loops pick positions i < j < k. A triple that sums to 0 is sorted numerically and stored in a Map<string, number[]> under a template-literal key such as "-5,2,3". The string key is what removes repeats: two arrays with the same numbers are still different objects, so a Set<number[]> would keep both. Finding [-5, 2, 3] again through the second 2 just overwrites the same entry.
function threeSum(nums: number[]): number[][] {
const found = new Map<string, number[]>(); // "a,b,c" -> [a, b, c]
const n = nums.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] === 0) {
const triplet = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
found.set(`${triplet[0]},${triplet[1]},${triplet[2]}`, triplet);
}
}
}
}
return [...found.values()];
}
Sort a copy first, so equal values are neighbours and each triplet is built in ascending order. For each distinct first value sorted[i], walk j to the right with a Set<number> of the values passed since i; the third number is 0 - sorted[i] - sorted[j], and has answers in constant time on average. Checking before add keeps a position from pairing with itself, and after a hit the loop skips the following copies of sorted[j], so no triplet is recorded twice and no string keys are needed.
function threeSum(nums: number[]): number[][] {
const sorted = [...nums].sort((a, b) => a - b); // a copy: the caller's array is untouched
const result: number[][] = [];
for (let i = 0; i < sorted.length - 2; i++) {
if (i > 0 && sorted[i] === sorted[i - 1]) continue; // same first value, same triplets
const seen = new Set<number>(); // values between position i and position j
for (let j = i + 1; j < sorted.length; j++) {
const need = 0 - sorted[i] - sorted[j]; // 0 - ... avoids a -0
if (seen.has(need)) {
result.push([sorted[i], need, sorted[j]]);
while (j + 1 < sorted.length && sorted[j + 1] === sorted[j]) j++; // same third value
}
seen.add(sorted[j]);
}
}
return result;
}
Sort with (a, b) => a - b, then for each first value put lo just after it and hi at the end. A sum below 0 can only rise by moving lo right, a sum above 0 can only fall by moving hi left, and a zero sum is a triplet to push before moving both. One === against the previous element skips a repeated first or middle value, and once nums[i] is positive no later triplet can reach 0. The sort is O(n log n), the scan O(n²), and nothing but the result grows with n; the price is that nums.sort reorders the caller's array.
function threeSum(nums: number[]): number[][] {
nums.sort((a, b) => a - b); // numeric order, in place
const result: number[][] = [];
for (let i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) break; // three positive numbers can't sum to 0
if (i > 0 && nums[i] === nums[i - 1]) continue; // same first value, same triplets
let lo = i + 1;
let hi = nums.length - 1;
while (lo < hi) {
const sum = nums[i] + nums[lo] + nums[hi];
if (sum < 0) {
lo++;
} else if (sum > 0) {
hi--;
} else {
result.push([nums[i], nums[lo], nums[hi]]);
lo++;
hi--;
while (lo < hi && nums[lo] === nums[lo - 1]) lo++; // skip repeats of the middle value
}
}
}
return result;
}
3Sum in Java
3 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.
Three nested loops with i < j < k try every index triple. A zero sum is copied into a small int[], put in order with Arrays.sort, and boxed into List.of(t[0], t[1], t[2]) before it goes into a HashSet. The list is what makes de-duplication work: List defines equals and hashCode over its elements, while an int[] keeps the identity-based versions inherited from Object. HashSet promises no iteration order, so toArray copies the set into an int[][] and sorts it with Arrays::compare, which orders two int[] element by element.
import java.util.*;
public class Main {
static int[][] threeSum(int[] nums) {
Set<List<Integer>> found = new HashSet<>(); // lists compare by value, arrays do not
int n = nums.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
int[] t = {nums[i], nums[j], nums[k]};
Arrays.sort(t);
found.add(List.of(t[0], t[1], t[2]));
}
}
}
}
return toArray(found);
}
static int[][] toArray(Set<List<Integer>> found) {
int[][] result = new int[found.size()][];
int r = 0;
for (List<Integer> t : found) {
result[r++] = new int[] {t.get(0), t.get(1), t.get(2)};
}
Arrays.sort(result, Arrays::compare); // HashSet order is not guaranteed
return result;
}
}
Once nums[i] is fixed, the rest of the array only has to supply a pair totalling -nums[i]. A HashSet<Integer> named seen collects each nums[j] after it has been tested, so seen.contains(need) tells you in average constant time whether the missing third value showed up between i and j. Order inside the loop matters: contains runs before add, so nums[j] can never pair with itself. That lookup takes over the job of the k loop; autoboxing wraps each int as an Integer on the way in, which is heavier than working on the raw array. The Set<List<Integer>> and the sorted copy remain for de-duplication and order.
import java.util.*;
public class Main {
static int[][] threeSum(int[] nums) {
Set<List<Integer>> found = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
Set<Integer> seen = new HashSet<>(); // values between position i and position j
for (int j = i + 1; j < nums.length; j++) {
int need = -nums[i] - nums[j];
if (seen.contains(need)) {
int[] t = {nums[i], need, nums[j]};
Arrays.sort(t);
found.add(List.of(t[0], t[1], t[2]));
}
seen.add(nums[j]);
}
}
return toArray(found);
}
static int[][] toArray(Set<List<Integer>> found) {
int[][] result = new int[found.size()][];
int r = 0;
for (List<Integer> t : found) {
result[r++] = new int[] {t.get(0), t.get(1), t.get(2)};
}
Arrays.sort(result, Arrays::compare); // HashSet order is not guaranteed
return result;
}
}
Sort the int[], then for each nums[i] start lo at i + 1 and hi at nums.length - 1. A total below zero can only grow by advancing lo; a total above zero can only shrink by pulling hi back. A zero total is added as a fresh int[], and both ends move. Sorted order puts duplicates next to each other, so a single nums[i] == nums[i - 1] test skips a repeated first value, and the same idea skips a repeated middle value. The == tests are safe because they compare primitives. Arrays.sort on an int[] is O(n log n), followed by O(n²) scanning; the method sorts the array it receives, so call it with nums.clone() to keep the caller's order.
import java.util.*;
public class Main {
static int[][] threeSum(int[] nums) {
Arrays.sort(nums); // sorts the caller's array in place
List<int[]> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) {
break; // three positive numbers can't sum to 0
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue; // same first value, same triplets
}
int lo = i + 1;
int hi = nums.length - 1;
while (lo < hi) {
int sum = nums[i] + nums[lo] + nums[hi];
if (sum < 0) {
lo++;
} else if (sum > 0) {
hi--;
} else {
result.add(new int[] {nums[i], nums[lo], nums[hi]});
lo++;
hi--;
while (lo < hi && nums[lo] == nums[lo - 1]) {
lo++; // skip repeats of the middle value
}
}
}
}
return result.toArray(new int[0][]);
}
}
3Sum in Go
3 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.
Three nested for loops visit every index triple with i < j < k. A hit is copied into a [3]int, sorted through the slice expression t[:] (which shares the array's storage, so the array itself ends up sorted), and used as a key in map[[3]int]struct{}. Go accepts a fixed-size array as a key because arrays are comparable; a []int key is rejected at compile time. Ranging over a map yields a different order from run to run, so the keys are copied into a [][]int and ordered with slices.SortFunc(result, slices.Compare) so the output is easy to read.
package main
import "slices"
func threeSum(nums []int) [][]int {
found := map[[3]int]struct{}{} // arrays can be map keys, slices cannot
n := len(nums)
for i := range n {
for j := i + 1; j < n; j++ {
for k := j + 1; k < n; k++ {
if nums[i]+nums[j]+nums[k] == 0 {
t := [3]int{nums[i], nums[j], nums[k]}
slices.Sort(t[:])
found[t] = struct{}{}
}
}
}
}
result := make([][]int, 0, len(found))
for t := range found {
result = append(result, []int{t[0], t[1], t[2]})
}
slices.SortFunc(result, slices.Compare) // map order is random
return result
}
Pick nums[i] as the first value and what remains is a pair search: two later elements whose total is -nums[i]. As j walks right, a map called seen remembers the values between i and j. The comma-ok form _, ok := seen[need] is how you test membership here, since an empty struct value carries nothing to check. Looking up need before inserting nums[j] is what stops an element pairing with itself. That average O(1) lookup stands in for the third loop; the [3]int key set and the closing sort stay, for de-duplication and order.
package main
import "slices"
func threeSum(nums []int) [][]int {
found := map[[3]int]struct{}{}
for i := range nums {
seen := map[int]struct{}{} // values between position i and position j
for j := i + 1; j < len(nums); j++ {
need := -nums[i] - nums[j]
if _, ok := seen[need]; ok {
t := [3]int{nums[i], need, nums[j]}
slices.Sort(t[:])
found[t] = struct{}{}
}
seen[nums[j]] = struct{}{}
}
}
result := make([][]int, 0, len(found))
for t := range found {
result = append(result, []int{t[0], t[1], t[2]})
}
slices.SortFunc(result, slices.Compare) // map order is random
return result
}
With the slice sorted, each nums[i] gets two indexes: lo right after it and hi on the last element. A tagless switch picks the move. A negative sum needs a bigger value, so lo++; a positive one needs a smaller value, so hi--; zero is a triplet, and both indexes step inward. Sorting also groups equal numbers, so one comparison with the previous element skips a repeat, and the map from the earlier versions is gone. Ranging over a negative count such as len(nums) - 2 does nothing, so the empty slice returns the untouched nil result. slices.Sort(nums) reorders the caller's data; hand in slices.Clone(nums) to keep it.
package main
import "slices"
func threeSum(nums []int) [][]int {
slices.Sort(nums) // sorts the caller's slice in place
var result [][]int
for i := range len(nums) - 2 {
if nums[i] > 0 {
break // three positive numbers can't sum to 0
}
if i > 0 && nums[i] == nums[i-1] {
continue // same first value, same triplets
}
lo, hi := i+1, len(nums)-1
for lo < hi {
sum := nums[i] + nums[lo] + nums[hi]
switch {
case sum < 0:
lo++
case sum > 0:
hi--
default:
result = append(result, []int{nums[i], nums[lo], nums[hi]})
lo++
hi--
for lo < hi && nums[lo] == nums[lo-1] {
lo++ // skip repeats of the middle value
}
}
}
}
return result
}
3Sum in C#
3 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.
Three nested loops with i < j < k visit every triple of positions. A zero sum is copied into a three-element array, put in order with Array.Sort, and stored as a (int, int, int) value tuple in a HashSet. The tuple is what makes the de-duplication work: value tuples compare and hash by their elements, while an int[] keeps the reference-based Equals and GetHashCode from Object, so a set of arrays would keep every copy. At the end each tuple is turned back into an int[] and the list becomes the int[][] the signature asks for; sorting the tuples first just gives a predictable order.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int[][] ThreeSum(int[] nums)
{
var found = new HashSet<(int, int, int)>(); // value tuples compare by value, arrays do not
int n = nums.Length;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
for (int k = j + 1; k < n; k++)
{
if (nums[i] + nums[j] + nums[k] == 0)
{
int[] t = { nums[i], nums[j], nums[k] };
Array.Sort(t);
found.Add((t[0], t[1], t[2]));
}
}
}
}
return ToArray(found);
}
static int[][] ToArray(HashSet<(int, int, int)> found)
{
var result = new List<int[]>();
foreach (var (a, b, c) in found.OrderBy(t => t)) // HashSet order is not guaranteed
{
result.Add(new[] { a, b, c });
}
return result.ToArray();
}
}
Fix nums[i] and the rest of the array only has to supply a pair that adds up to -nums[i], which is Two Sum. Walk j to the right with a HashSet<int> of the values passed since i; seen.Contains(need) answers in constant time on average whether the missing third value sits between i and j. The check runs before seen.Add(nums[j]), so a value never pairs with itself. That lookup replaces the k loop. The set of sorted tuples stays, because the same three values can still be reached from different positions, and the set is rebuilt for every i rather than cleared, so no stale value from an earlier pass leaks in.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int[][] ThreeSum(int[] nums)
{
var found = new HashSet<(int, int, int)>();
for (int i = 0; i < nums.Length; i++)
{
var seen = new HashSet<int>(); // values between position i and position j
for (int j = i + 1; j < nums.Length; j++)
{
int need = -nums[i] - nums[j];
if (seen.Contains(need))
{
int[] t = { nums[i], need, nums[j] };
Array.Sort(t);
found.Add((t[0], t[1], t[2]));
}
seen.Add(nums[j]);
}
}
return ToArray(found);
}
static int[][] ToArray(HashSet<(int, int, int)> found)
{
var result = new List<int[]>();
foreach (var (a, b, c) in found.OrderBy(t => t)) // HashSet order is not guaranteed
{
result.Add(new[] { a, b, c });
}
return result.ToArray();
}
}
Array.Sort the array, then for each first value nums[i] start lo at i + 1 and hi at the last index. A sum below zero can only rise by moving lo right; a sum above zero can only fall by moving hi left. On a match, add a fresh int[] to the List<int[]> and move both ends. Sorting puts equal values next to each other, so one nums[i] == nums[i - 1] comparison skips a repeated first value and the same test skips a repeated middle value, which is why no set is needed. Once nums[i] is positive, everything to its right is positive too, so the loop can stop. The sort is O(n log n), the scan O(n²), and only the result grows. The method sorts the array it is given; pass (int[]) nums.Clone() if the caller must keep its order.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int[][] ThreeSum(int[] nums)
{
Array.Sort(nums); // sorts the caller's array in place
var result = new List<int[]>();
for (int i = 0; i < nums.Length - 2; i++)
{
if (nums[i] > 0) break; // three positive numbers can't sum to 0
if (i > 0 && nums[i] == nums[i - 1]) continue; // same first value, same triplets
int lo = i + 1;
int hi = nums.Length - 1;
while (lo < hi)
{
int sum = nums[i] + nums[lo] + nums[hi];
if (sum < 0)
{
lo++;
}
else if (sum > 0)
{
hi--;
}
else
{
result.Add(new[] { nums[i], nums[lo], nums[hi] });
lo++;
hi--;
while (lo < hi && nums[lo] == nums[lo - 1]) lo++; // skip repeats of the middle value
}
}
}
return result.ToArray();
}
}
3Sum in C++
3 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.
Three loops pick positions i < j < k. A triple that sums to 0 is put in order with std::sort and inserted into a set<vector<int>>. Unlike a raw array, vector compares by its elements, so the set treats a second {-5, 2, 3} built from another 2 as the same key and ignores it. The result is constructed straight from the set's iterator range.
#include <algorithm>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> found; // vectors compare element by element
int n = (int)nums.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
vector<int> t = {nums[i], nums[j], nums[k]};
sort(t.begin(), t.end());
found.insert(t);
}
}
}
}
return vector<vector<int>>(found.begin(), found.end());
}
};
Fix nums[i] and look for two later values that add up to -nums[i]. While j moves right, an unordered_set<int> holds the values passed since i, and count(need) answers in constant average time, which removes the third loop. Testing before insert keeps a position from pairing with itself. Repeats are still possible, so the sorted triplets go into a set<vector<int>> as before.
#include <algorithm>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> found;
int n = (int)nums.size();
for (int i = 0; i < n; i++) {
unordered_set<int> seen; // values between position i and position j
for (int j = i + 1; j < n; j++) {
int need = -nums[i] - nums[j];
if (seen.count(need)) {
vector<int> t = {nums[i], need, nums[j]};
sort(t.begin(), t.end());
found.insert(t);
}
seen.insert(nums[j]);
}
}
return vector<vector<int>>(found.begin(), found.end());
}
};
sort(nums.begin(), nums.end()), then for each first value put lo just after it and hi at the end. A sum below 0 can only rise by moving lo right, a sum above 0 can only fall by moving hi left, and a zero sum is pushed with push_back({…}) before both move. Equal values are neighbours now, so one comparison with the previous element skips a repeated first or middle value and no set is needed. The sort is O(n log n) and the scan O(n²); because nums arrives by reference, the caller's vector ends up sorted.
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end()); // sorts the caller's vector in place
vector<vector<int>> result;
int n = (int)nums.size();
for (int i = 0; i + 2 < n; i++) {
if (nums[i] > 0) break; // three positive numbers can't sum to 0
if (i > 0 && nums[i] == nums[i - 1]) continue; // same first value, same triplets
int lo = i + 1, hi = n - 1;
while (lo < hi) {
int sum = nums[i] + nums[lo] + nums[hi];
if (sum < 0) {
lo++;
} else if (sum > 0) {
hi--;
} else {
result.push_back({nums[i], nums[lo], nums[hi]});
lo++;
hi--;
while (lo < hi && nums[lo] == nums[lo - 1]) lo++; // skip repeats of the middle value
}
}
}
return result;
}
};
3Sum in C
3 reference approaches in C, from brute force to the one to reach for. Compare them with yours.
C has no set of tuples to drop repeated triplets, so sort a malloc'ed copy with qsort first. Three loops then pick i < j < k, and each loop skips a value equal to the one it just tried, so every triplet of values is visited once and comes out in ascending order. A hit is appended to a growing row array (realloc doubles it) and the inner loop stops, since a larger third value cannot also reach 0. At the end *returnSize is the count and *returnColumnSizes is a fresh array of 3s.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int** rows;
int count;
int capacity;
} Triplets;
static void add_triplet(Triplets* t, int a, int b, int c) {
if (t->count == t->capacity) {
t->capacity = t->capacity ? 2 * t->capacity : 16;
t->rows = realloc(t->rows, t->capacity * sizeof *t->rows);
}
int* row = malloc(3 * sizeof *row);
row[0] = a;
row[1] = b;
row[2] = c;
t->rows[t->count++] = row;
}
static int** finish(Triplets* t, int* returnSize, int** returnColumnSizes) {
*returnSize = t->count;
*returnColumnSizes = malloc((t->count ? t->count : 1) * sizeof **returnColumnSizes);
for (int r = 0; r < t->count; r++) (*returnColumnSizes)[r] = 3;
return t->rows;
}
static int compare_ints(const void* x, const void* y) {
int a = *(const int*)x, b = *(const int*)y;
return (a > b) - (a < b);
}
static int* sorted_copy(const int* nums, int numsSize) {
int* a = malloc((numsSize ? numsSize : 1) * sizeof *a);
if (numsSize) memcpy(a, nums, numsSize * sizeof *a);
qsort(a, numsSize, sizeof *a, compare_ints);
return a;
}
/**
* Note: the returned arrays and *returnColumnSizes must be malloc'ed; the caller frees them.
*/
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
int* a = sorted_copy(nums, numsSize); // sorted, so equal values are neighbours
Triplets t = {NULL, 0, 0};
for (int i = 0; i < numsSize; i++) {
if (i > 0 && a[i] == a[i - 1]) continue;
for (int j = i + 1; j < numsSize; j++) {
if (j > i + 1 && a[j] == a[j - 1]) continue;
for (int k = j + 1; k < numsSize; k++) {
if (k > j + 1 && a[k] == a[k - 1]) continue;
if (a[i] + a[j] + a[k] == 0) {
add_triplet(&t, a[i], a[j], a[k]);
break; // a larger third value can't also reach 0
}
}
}
}
free(a);
return finish(&t, returnSize, returnColumnSizes);
}
Fix the first value and look for two later values that add up to -a[i]. C has no built-in hash set, so this builds an open-addressing table of ints twice the input's size; instead of clearing it for every i, a slot counts as used only when its round stamp equals the current round. De-duplication again comes from the sorted copy: a repeated first value is skipped, and after a hit the loop jumps past the copies of a[j]. The lookup happens before the insert, so a position never pairs with itself.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int** rows;
int count;
int capacity;
} Triplets;
static void add_triplet(Triplets* t, int a, int b, int c) {
if (t->count == t->capacity) {
t->capacity = t->capacity ? 2 * t->capacity : 16;
t->rows = realloc(t->rows, t->capacity * sizeof *t->rows);
}
int* row = malloc(3 * sizeof *row);
row[0] = a;
row[1] = b;
row[2] = c;
t->rows[t->count++] = row;
}
static int** finish(Triplets* t, int* returnSize, int** returnColumnSizes) {
*returnSize = t->count;
*returnColumnSizes = malloc((t->count ? t->count : 1) * sizeof **returnColumnSizes);
for (int r = 0; r < t->count; r++) (*returnColumnSizes)[r] = 3;
return t->rows;
}
static int compare_ints(const void* x, const void* y) {
int a = *(const int*)x, b = *(const int*)y;
return (a > b) - (a < b);
}
static int* sorted_copy(const int* nums, int numsSize) {
int* a = malloc((numsSize ? numsSize : 1) * sizeof *a);
if (numsSize) memcpy(a, nums, numsSize * sizeof *a);
qsort(a, numsSize, sizeof *a, compare_ints);
return a;
}
static unsigned slot_of(int key, unsigned mask) {
return (unsigned)key * 2654435761u & mask; // unsigned math wraps, no overflow
}
static bool contains(const int* keys, const int* round, int now, unsigned mask, int key) {
for (unsigned s = slot_of(key, mask); round[s] == now; s = (s + 1) & mask) {
if (keys[s] == key) return true;
}
return false;
}
static void insert(int* keys, int* round, int now, unsigned mask, int key) {
unsigned s = slot_of(key, mask);
while (round[s] == now && keys[s] != key) s = (s + 1) & mask;
round[s] = now;
keys[s] = key;
}
/**
* Note: the returned arrays and *returnColumnSizes must be malloc'ed; the caller frees them.
*/
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
int* a = sorted_copy(nums, numsSize);
int capacity = 1;
while (capacity < 2 * numsSize) capacity <<= 1;
unsigned mask = (unsigned)(capacity - 1);
int* keys = malloc(capacity * sizeof *keys);
int* round = calloc(capacity, sizeof *round); // a slot is used when round[slot] == i + 1
Triplets t = {NULL, 0, 0};
for (int i = 0; i + 2 < numsSize; i++) {
if (i > 0 && a[i] == a[i - 1]) continue; // same first value, same triplets
for (int j = i + 1; j < numsSize; j++) {
int need = -a[i] - a[j];
if (contains(keys, round, i + 1, mask, need)) {
add_triplet(&t, a[i], need, a[j]);
while (j + 1 < numsSize && a[j + 1] == a[j]) j++; // same third value
}
insert(keys, round, i + 1, mask, a[j]);
}
}
free(a);
free(keys);
free(round);
return finish(&t, returnSize, returnColumnSizes);
}
Sort a copy with qsort, then for each first value put lo just after it and hi at the end. A sum below 0 can only rise by moving lo right, a sum above 0 can only fall by moving hi left, and a zero sum is appended before both move. One comparison with the previous element skips a repeated first or middle value, and a positive first value ends the search. Apart from the copy and the result, nothing grows with n; the caller's array keeps its order.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int** rows;
int count;
int capacity;
} Triplets;
static void add_triplet(Triplets* t, int a, int b, int c) {
if (t->count == t->capacity) {
t->capacity = t->capacity ? 2 * t->capacity : 16;
t->rows = realloc(t->rows, t->capacity * sizeof *t->rows);
}
int* row = malloc(3 * sizeof *row);
row[0] = a;
row[1] = b;
row[2] = c;
t->rows[t->count++] = row;
}
static int** finish(Triplets* t, int* returnSize, int** returnColumnSizes) {
*returnSize = t->count;
*returnColumnSizes = malloc((t->count ? t->count : 1) * sizeof **returnColumnSizes);
for (int r = 0; r < t->count; r++) (*returnColumnSizes)[r] = 3;
return t->rows;
}
static int compare_ints(const void* x, const void* y) {
int a = *(const int*)x, b = *(const int*)y;
return (a > b) - (a < b);
}
/**
* Note: the returned arrays and *returnColumnSizes must be malloc'ed; the caller frees them.
*/
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
int* a = malloc((numsSize ? numsSize : 1) * sizeof *a);
if (numsSize) memcpy(a, nums, numsSize * sizeof *a);
qsort(a, numsSize, sizeof *a, compare_ints);
Triplets t = {NULL, 0, 0};
for (int i = 0; i + 2 < numsSize; i++) {
if (a[i] > 0) break; // three positive numbers can't sum to 0
if (i > 0 && a[i] == a[i - 1]) continue; // same first value, same triplets
int lo = i + 1, hi = numsSize - 1;
while (lo < hi) {
int sum = a[i] + a[lo] + a[hi];
if (sum < 0) {
lo++;
} else if (sum > 0) {
hi--;
} else {
add_triplet(&t, a[i], a[lo], a[hi]);
lo++;
hi--;
while (lo < hi && a[lo] == a[lo - 1]) lo++; // skip repeats of the middle value
}
}
}
free(a);
return finish(&t, returnSize, returnColumnSizes);
}
3Sum in Kotlin
3 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.
Three nested until ranges try every index triple i < j < k. A zero sum becomes listOf(a, b, c).sorted() and goes into a HashSet<List<Int>>. A List compares by its elements, so the same triplet built from a different position is dropped; at the end each list is turned back into an IntArray with toIntArray().
class Solution {
fun threeSum(nums: IntArray): Array<IntArray> {
val found = HashSet<List<Int>>() // lists compare by value, IntArray does not
val n = nums.size
for (i in 0 until n) {
for (j in i + 1 until n) {
for (k in j + 1 until n) {
if (nums[i] + nums[j] + nums[k] == 0) {
found.add(listOf(nums[i], nums[j], nums[k]).sorted())
}
}
}
}
return found.map { it.toIntArray() }.toTypedArray()
}
}
Fix nums[i] and look for a pair that adds up to -nums[i] among the later numbers. A fresh HashSet<Int> holds the values passed since i; need in seen runs before seen.add(nums[j]), so a position never pairs with itself. The set lookup replaces the k loop, and the HashSet<List<Int>> still removes repeated triplets.
class Solution {
fun threeSum(nums: IntArray): Array<IntArray> {
val found = HashSet<List<Int>>()
for (i in nums.indices) {
val seen = HashSet<Int>() // values between position i and position j
for (j in i + 1 until nums.size) {
val need = -nums[i] - nums[j]
if (need in seen) {
found.add(listOf(nums[i], need, nums[j]).sorted())
}
seen.add(nums[j])
}
}
return found.map { it.toIntArray() }.toTypedArray()
}
}
nums.sorted() returns a sorted List<Int> copy, so the caller's array keeps its order. For each first value, lo starts just after it and hi at the end; a when on the sum moves lo right when it is too small and hi left when it is too big. Equal values are neighbours after sorting, so one comparison with the previous element skips repeats and no set is needed. Matches are collected in a mutableListOf<IntArray>() and returned with toTypedArray().
class Solution {
fun threeSum(nums: IntArray): Array<IntArray> {
val sorted = nums.sorted() // a sorted copy; nums keeps its order
val result = mutableListOf<IntArray>()
for (i in sorted.indices) {
if (sorted[i] > 0) break // three positive numbers can't sum to 0
if (i > 0 && sorted[i] == sorted[i - 1]) continue // same first value, same triplets
var lo = i + 1
var hi = sorted.size - 1
while (lo < hi) {
val sum = sorted[i] + sorted[lo] + sorted[hi]
when {
sum < 0 -> lo++
sum > 0 -> hi--
else -> {
result.add(intArrayOf(sorted[i], sorted[lo], sorted[hi]))
lo++
hi--
while (lo < hi && sorted[lo] == sorted[lo - 1]) lo++ // skip repeats of the middle value
}
}
}
}
return result.toTypedArray()
}
}
3Sum in Rust
3 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.
Three nested ranges try every index triple i < j < k. A zero sum is copied into a fixed-size [i32; 3], put in order with sort_unstable, and inserted into a HashSet<[i32; 3]>. Arrays implement Hash and Eq by value, so a repeated triplet is ignored, and nothing is heap-allocated until to_vec builds the result.
use std::collections::HashSet;
impl Solution {
pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
let n = nums.len();
let mut found: HashSet<[i32; 3]> = HashSet::new();
for i in 0..n {
for j in i + 1..n {
for k in j + 1..n {
if nums[i] + nums[j] + nums[k] == 0 {
let mut t = [nums[i], nums[j], nums[k]];
t.sort_unstable();
found.insert(t);
}
}
}
}
found.into_iter().map(|t| t.to_vec()).collect()
}
}
Fix a = nums[i] and walk the slice &nums[i + 1..], keeping the values passed so far in a HashSet<i32>. seen.contains(&need) runs before seen.insert(b), so a position never pairs with itself, and the lookup replaces the k loop. The HashSet<[i32; 3]> of sorted triplets still removes repeats.
use std::collections::HashSet;
impl Solution {
pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut found: HashSet<[i32; 3]> = HashSet::new();
for (i, &a) in nums.iter().enumerate() {
let mut seen: HashSet<i32> = HashSet::new(); // values between position i and the current one
for &b in &nums[i + 1..] {
let need = -a - b;
if seen.contains(&need) {
let mut t = [a, need, b];
t.sort_unstable();
found.insert(t);
}
seen.insert(b);
}
}
found.into_iter().map(|t| t.to_vec()).collect()
}
}
The function takes mut nums, which it owns, and sorts it with sort_unstable. For each first value, lo starts just after it and hi at the end; a match on sum.cmp(&0) moves lo right on Ordering::Less and hi left on Ordering::Greater. Sorted order puts equal values side by side, so one comparison with the previous element skips repeats without a set.
use std::cmp::Ordering;
impl Solution {
pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
nums.sort_unstable(); // the Vec is owned here, so sorting it is free to do
let mut result = Vec::new();
for i in 0..nums.len() {
if nums[i] > 0 {
break; // three positive numbers can't sum to 0
}
if i > 0 && nums[i] == nums[i - 1] {
continue; // same first value, same triplets
}
let (mut lo, mut hi) = (i + 1, nums.len() - 1);
while lo < hi {
match (nums[i] + nums[lo] + nums[hi]).cmp(&0) {
Ordering::Less => lo += 1,
Ordering::Greater => hi -= 1,
Ordering::Equal => {
result.push(vec![nums[i], nums[lo], nums[hi]]);
lo += 1;
hi -= 1;
while lo < hi && nums[lo] == nums[lo - 1] {
lo += 1; // skip repeats of the middle value
}
}
}
}
}
result
}
}
3Sum in Swift
3 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.
Three nested half-open ranges try every index triple i < j < k. A zero sum is sorted with sorted() and inserted into a Set<[Int]>. Arrays of a Hashable element are Hashable themselves and compare by value, so a triplet found again from different positions is ignored. Array(found) turns the set into the result.
class Solution {
func threeSum(_ nums: [Int]) -> [[Int]] {
var found = Set<[Int]>() // [Int] is Hashable and compares by value
let n = nums.count
for i in 0..<n {
for j in (i + 1)..<n {
for k in (j + 1)..<n where nums[i] + nums[j] + nums[k] == 0 {
found.insert([nums[i], nums[j], nums[k]].sorted())
}
}
}
return Array(found)
}
}
Fix nums[i] and look among the later numbers for a pair that adds up to -nums[i]. A fresh Set<Int> holds the values passed since i; seen.contains(need) runs before seen.insert(nums[j]), so a position never pairs with itself. The lookup takes the place of the k loop, and the Set<[Int]> of sorted triplets still removes repeats.
class Solution {
func threeSum(_ nums: [Int]) -> [[Int]] {
var found = Set<[Int]>()
for i in nums.indices {
var seen = Set<Int>() // values between position i and position j
for j in (i + 1)..<nums.count {
let need = -nums[i] - nums[j]
if seen.contains(need) {
found.insert([nums[i], need, nums[j]].sorted())
}
seen.insert(nums[j])
}
}
return Array(found)
}
}
Parameters are constants and arrays are values, so let nums = nums.sorted() shadows the argument with a sorted copy. For each first value, lo starts just after it and hi at the end: a sum below 0 moves lo right, above 0 moves hi left. Equal values are neighbours after sorting, so one comparison with the previous element skips repeats and no set is needed.
class Solution {
func threeSum(_ nums: [Int]) -> [[Int]] {
let nums = nums.sorted() // a sorted copy; the caller's array is untouched
var result: [[Int]] = []
for i in nums.indices {
if nums[i] > 0 { break } // three positive numbers can't sum to 0
if i > 0 && nums[i] == nums[i - 1] { continue } // same first value, same triplets
var lo = i + 1
var hi = nums.count - 1
while lo < hi {
let sum = nums[i] + nums[lo] + nums[hi]
if sum < 0 {
lo += 1
} else if sum > 0 {
hi -= 1
} else {
result.append([nums[i], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi && nums[lo] == nums[lo - 1] {
lo += 1 // skip repeats of the middle value
}
}
}
}
return result
}
}
3Sum in PHP
3 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.
Three nested for loops try every index triple $i < $j < $k. A zero sum is put in order with sort and stored in $found under the key implode(',', $t), so the same three values found again overwrite one entry instead of adding a second. array_values drops the string keys, leaving the list of triplets the signature expects.
<?php
class Solution {
/**
* @param int[] $nums
* @return int[][]
*/
function threeSum(array $nums): array {
$found = []; // "a,b,c" => [a, b, c]
$n = count($nums);
for ($i = 0; $i < $n; $i++) {
for ($j = $i + 1; $j < $n; $j++) {
for ($k = $j + 1; $k < $n; $k++) {
if ($nums[$i] + $nums[$j] + $nums[$k] === 0) {
$t = [$nums[$i], $nums[$j], $nums[$k]];
sort($t);
$found[implode(',', $t)] = $t;
}
}
}
}
return array_values($found);
}
}
Fix $nums[$i] and look among the later numbers for a pair that adds up to -$nums[$i]. The array $seen uses the values passed since $i as keys, so isset($seen[$need]) is a constant-time lookup that replaces the $k loop. The check runs before $seen[$nums[$j]] = true, so a position never pairs with itself; the string-keyed $found still removes repeats.
<?php
class Solution {
/**
* @param int[] $nums
* @return int[][]
*/
function threeSum(array $nums): array {
$found = [];
$n = count($nums);
for ($i = 0; $i < $n; $i++) {
$seen = []; // values between position $i and position $j, as keys
for ($j = $i + 1; $j < $n; $j++) {
$need = -$nums[$i] - $nums[$j];
if (isset($seen[$need])) {
$t = [$nums[$i], $need, $nums[$j]];
sort($t);
$found[implode(',', $t)] = $t;
}
$seen[$nums[$j]] = true;
}
}
return array_values($found);
}
}
sort($nums) reorders the method's own copy: PHP passes arrays by value, so the caller's array is untouched. For each first value, $lo starts just after it and $hi at the end; a sum below 0 moves $lo right, above 0 moves $hi left. Equal values are neighbours after sorting, so one comparison with the previous element skips repeats, and $result[] = … builds a plain list.
<?php
class Solution {
/**
* @param int[] $nums
* @return int[][]
*/
function threeSum(array $nums): array {
sort($nums); // sorts this method's copy; arrays are passed by value
$result = [];
$n = count($nums);
for ($i = 0; $i < $n - 2; $i++) {
if ($nums[$i] > 0) {
break; // three positive numbers can't sum to 0
}
if ($i > 0 && $nums[$i] === $nums[$i - 1]) {
continue; // same first value, same triplets
}
$lo = $i + 1;
$hi = $n - 1;
while ($lo < $hi) {
$sum = $nums[$i] + $nums[$lo] + $nums[$hi];
if ($sum < 0) {
$lo++;
} elseif ($sum > 0) {
$hi--;
} else {
$result[] = [$nums[$i], $nums[$lo], $nums[$hi]];
$lo++;
$hi--;
while ($lo < $hi && $nums[$lo] === $nums[$lo - 1]) {
$lo++; // skip repeats of the middle value
}
}
}
}
return $result;
}
}
3Sum in Ruby
3 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.
Three nested exclusive ranges try every index triple i < j < k. A zero sum is sorted and added to a Set. Ruby arrays define eql? and hash by their elements, so the same triplet found from other positions is stored once, and to_a returns the set as the list of triplets.
require 'set'
# @param {Integer[]} nums
# @return {Integer[][]}
def three_sum(nums)
found = Set.new # arrays hash by value, so a repeated triplet is ignored
n = nums.length
(0...n).each do |i|
a = nums[i]
((i + 1)...n).each do |j|
b = nums[j]
((j + 1)...n).each do |k|
found << [a, b, nums[k]].sort if a + b + nums[k] == 0
end
end
end
found.to_a
end
Fix a = nums[i] and look among the later numbers for a pair that adds up to -a. A fresh Set named seen holds the values passed since i; seen.include?(need) runs before seen << b, so a position never pairs with itself. The lookup replaces the k loop, and the outer Set of sorted arrays still removes repeats.
require 'set'
# @param {Integer[]} nums
# @return {Integer[][]}
def three_sum(nums)
found = Set.new
nums.each_with_index do |a, i|
seen = Set.new # values between position i and the current one
nums[(i + 1)..].each do |b|
need = -a - b
found << [a, need, b].sort if seen.include?(need)
seen << b
end
end
found.to_a
end
nums.sort returns a sorted copy, leaving the argument alone. For each first value, lo starts just after it and hi at the end, and a case on sum <=> 0 moves lo right on -1 and hi left on 1. Equal values sit side by side after sorting, so next skips a repeated first value and a short while skips a repeated middle one.
# @param {Integer[]} nums
# @return {Integer[][]}
def three_sum(nums)
nums = nums.sort # a sorted copy; the caller's array keeps its order
result = []
nums.each_with_index do |a, i|
break if a > 0 # three positive numbers can't sum to 0
next if i > 0 && a == nums[i - 1] # same first value, same triplets
lo = i + 1
hi = nums.length - 1
while lo < hi
case (a + nums[lo] + nums[hi]) <=> 0
when -1 then lo += 1
when 1 then hi -= 1
else
result << [a, nums[lo], nums[hi]]
lo += 1
hi -= 1
lo += 1 while lo < hi && nums[lo] == nums[lo - 1] # skip repeats of the middle value
end
end
end
result
end
3Sum in Dart
3 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.
Three nested for loops try every index triple i < j < k. A zero sum is sorted with the cascade [a, b, c]..sort() and turned into a key with join(','). Set.add returns true only for a new key, so the triplet is appended to the result just once, however many positions produce it.
class Solution {
List<List<int>> threeSum(List<int> nums) {
final keys = <String>{}; // lists compare by identity, strings by value
final result = <List<int>>[];
final n = nums.length;
for (var i = 0; i < n; i++) {
for (var j = i + 1; j < n; j++) {
for (var k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
final t = [nums[i], nums[j], nums[k]]..sort();
if (keys.add(t.join(','))) result.add(t);
}
}
}
}
return result;
}
}
Fix nums[i] and look among the later numbers for a pair that adds up to -nums[i]. A fresh Set<int> holds the values passed since i; seen.contains(need) runs before seen.add(nums[j]), so a position never pairs with itself. The lookup replaces the k loop, and the Set<String> of keys still removes repeated triplets.
class Solution {
List<List<int>> threeSum(List<int> nums) {
final keys = <String>{};
final result = <List<int>>[];
for (var i = 0; i < nums.length; i++) {
final seen = <int>{}; // values between position i and position j
for (var j = i + 1; j < nums.length; j++) {
final need = -nums[i] - nums[j];
if (seen.contains(need)) {
final t = [nums[i], need, nums[j]]..sort();
if (keys.add(t.join(','))) result.add(t);
}
seen.add(nums[j]);
}
}
return result;
}
}
[...nums]..sort() sorts a copy, so the caller's list keeps its order. For each first value, lo starts just after it and hi at the end: a sum below 0 moves lo right, above 0 moves hi left. Equal values are neighbours after sorting, so one comparison with the previous element skips repeats and no set is needed.
class Solution {
List<List<int>> threeSum(List<int> nums) {
final sorted = [...nums]..sort(); // a sorted copy; nums keeps its order
final result = <List<int>>[];
for (var i = 0; i < sorted.length - 2; i++) {
if (sorted[i] > 0) break; // three positive numbers can't sum to 0
if (i > 0 && sorted[i] == sorted[i - 1]) continue; // same first value, same triplets
var lo = i + 1;
var hi = sorted.length - 1;
while (lo < hi) {
final sum = sorted[i] + sorted[lo] + sorted[hi];
if (sum < 0) {
lo++;
} else if (sum > 0) {
hi--;
} else {
result.add([sorted[i], sorted[lo], sorted[hi]]);
lo++;
hi--;
while (lo < hi && sorted[lo] == sorted[lo - 1]) {
lo++; // skip repeats of the middle value
}
}
}
}
return result;
}
}
3Sum in Scala
3 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.
One for with three generators and a guard tries every index triple i < j < k whose values sum to 0. Each match becomes a sorted List[Int] in a mutable.HashSet; a List compares by its elements, so the same triplet found again is ignored. map(_.toArray).toArray builds the Array[Array[Int]] result.
import scala.collection.mutable
object Solution {
def threeSum(nums: Array[Int]): Array[Array[Int]] = {
val found = mutable.HashSet.empty[List[Int]] // lists compare by value, arrays do not
val n = nums.length
for {
i <- 0 until n
j <- i + 1 until n
k <- j + 1 until n
if nums(i) + nums(j) + nums(k) == 0
} found += List(nums(i), nums(j), nums(k)).sorted
found.iterator.map(_.toArray).toArray
}
}
Fix nums(i) and look among the later numbers for a pair that adds up to -nums(i). A fresh mutable.HashSet[Int] holds the values passed since i; seen.contains(need) runs before seen += nums(j), so a position never pairs with itself. The lookup takes over from the k loop, and the set of sorted List[Int] still removes repeats.
import scala.collection.mutable
object Solution {
def threeSum(nums: Array[Int]): Array[Array[Int]] = {
val found = mutable.HashSet.empty[List[Int]]
for (i <- nums.indices) {
val seen = mutable.HashSet.empty[Int] // values between position i and position j
for (j <- i + 1 until nums.length) {
val need = -nums(i) - nums(j)
if (seen.contains(need)) found += List(nums(i), need, nums(j)).sorted
seen += nums(j)
}
}
found.iterator.map(_.toArray).toArray
}
}
nums.sorted returns a sorted copy of the Array[Int]. Plain while loops do the walking: the outer one stops at the first positive value, which replaces a break, and a repeated first value is skipped with an if. For each first value lo starts just after it and hi at the end; a sum below 0 moves lo right, above 0 moves hi left, and matches go into an ArrayBuffer[Array[Int]].
import scala.collection.mutable.ArrayBuffer
object Solution {
def threeSum(nums: Array[Int]): Array[Array[Int]] = {
val s = nums.sorted // a sorted copy; nums keeps its order
val result = ArrayBuffer.empty[Array[Int]]
var i = 0
while (i < s.length - 2 && s(i) <= 0) { // three positive numbers can't sum to 0
if (i == 0 || s(i) != s(i - 1)) { // same first value, same triplets
var lo = i + 1
var hi = s.length - 1
while (lo < hi) {
val sum = s(i) + s(lo) + s(hi)
if (sum < 0) lo += 1
else if (sum > 0) hi -= 1
else {
result += Array(s(i), s(lo), s(hi))
lo += 1
hi -= 1
while (lo < hi && s(lo) == s(lo - 1)) lo += 1 // skip repeats of the middle value
}
}
}
i += 1
}
result.toArray
}
}
FAQ for Python
What if the target is not 0?
Pass the target in and compare against it instead of 0: if total < target moves lo right and elif total > target moves hi left. Drop the nums[i] > 0 early exit, which only holds for a target of 0. With target 2, [3, -1, -2, 5, -3, 0] gives [[-3, 0, 5], [-2, -1, 5], [-1, 0, 3]].
How do I solve 3Sum Closest?
In that variant you return the one sum closest to a target instead of a list of triplets. Keep the sort and the two pointers, track the best sum so far, replace it whenever abs(total - target) is smaller, and move the pointers by the same rule, returning at once if a sum equals the target. No duplicate skipping is needed because the answer is a single number. For [3, -1, -2, 5, -3, 0] and target 10 the answer is 8, from 0 + 3 + 5.
Why does sorting make skipping duplicates easy?
After sorting, equal values sit next to each other, so a repeat is just nums[i] == nums[i - 1]. Skipping a repeated first value avoids rebuilding the same triplets, and skipping a repeated middle value after a match avoids recording the same triplet twice. In an unsorted list equal values can be anywhere, which is why the first two approaches need a set of sorted tuples.
How do I return indices instead of values?
Sort the positions instead of the values: order = sorted(range(len(nums)), key=lambda p: nums[p]), run the same two pointers comparing nums[order[lo]] and nums[order[hi]], and on a match record sorted([order[i], order[lo], order[hi]]). For [3, -1, -2, 5, -3, 0] that gives [[0, 1, 2], [0, 4, 5], [2, 3, 4]] once the list is sorted. With repeated values it reports one index triplet per value triplet.
Can 3Sum be solved faster than O(n²)?
Not in any practical way. Sorting plus two pointers is the standard answer; algorithms that beat O(n²) by small logarithmic factors exist in theory but are not used in real code. What you can do is stop early, as the nums[i] > 0 check does once only positive values are left.
FAQ for JavaScript
Why can a Set not remove duplicate triplets on its own?
A Set compares objects by identity, and every [0, 0, 0] literal is a new array, so new Set([[0, 0, 0], [0, 0, 0]]).size is 2. Turn each sorted triplet into a primitive first: new Set(['0,0,0', '0,0,0']).size is 1. That is why the first two versions key a Map by triplet.join(',') and keep the array as the value.
Why do I get wrong triplets when I call sort() with no arguments?
Without a comparator, sort() converts the numbers to strings and orders them by character, so [3, -1, -2, 5, -3, 0].sort() gives [ -1, -2, -3, 0, 3, 5 ]. The two-pointer logic assumes the smallest value is on the left; on this order it returns [ [ -1, -2, 3 ], [ -2, -3, 5 ], [ -3, 0, 3 ] ], triplets that are not in ascending order. Always pass (a, b) => a - b.
Does threeSum change the array I pass in?
The two-pointer version does, because sort works in place: after threeSum(input) with input = [3, -1, -2, 5, -3, 0], logging input prints [ -3, -2, -1, 0, 3, 5 ]. Call threeSum([...input]) to keep the original order, or swap the first line for nums = nums.toSorted((a, b) => a - b). Both cost an O(n) copy.
Where does a -0 in the output come from?
From negating a zero. -0 - 0 evaluates to -0, and Node prints it as -0 inside an array, so computing need as -nums[i] - nums[j] makes [0, 0, 0, 0] come back as [ [ 0, -0, 0 ] ]. The lookup itself still works, since Set and === treat -0 and 0 as equal (-0 === 0 is true, Object.is(-0, 0) is false). Writing 0 - nums[i] - nums[j] gives a plain 0.
How do I adapt it to a target other than 0?
Add a target parameter, compare sum with target instead of 0, and delete the nums[i] > 0 early exit, which is only valid for zero. With target 2, [3, -1, -2, 5, -3, 0] returns [ [ -3, 0, 5 ], [ -2, -1, 5 ], [ -1, 0, 3 ] ]. For the closest-sum variant, keep the same pointer moves, remember the sum with the smallest Math.abs(sum - target), and return it: target 10 on the same array gives 8.
FAQ for TypeScript
Why does a Set<number[]> not remove duplicate triplets?
A Set compares objects by reference, and every [0, 0, 0] you build is a new array, so the set keeps each one. TypeScript accepts Set<number[]> without complaint because the type is fine; the bug only shows at runtime. Key a Map<string, number[]> by a string such as ${a},${b},${c}
Why pass (a, b) => a - b to sort when the array is typed number[]?
Types are erased before the code runs, and Array.prototype.sort with no comparator converts elements to strings, so [3, -1, -2, 10].sort() gives [-1, -2, 10, 3]. The number[] annotation does not change that. The two-pointer walk assumes true numeric order, so always pass the comparator.
Should the result type be [number, number, number][]?
A tuple array describes the answer more exactly than number[][], and callers then get a compile error if they read t[3]. Build each triplet with [a, b, c] as const or annotate the push, and the type checker enforces the length. The tests compare values, so either annotation passes.
Can I avoid mutating the caller's array?
Sort a copy: const sorted = [...nums].sort((a, b) => a - b), as the hash-set version does. On ES2023 targets nums.toSorted((a, b) => a - b) does the same in one call, but it needs lib: ["es2023"] in tsconfig.json and Node 20 or newer. Annotating the parameter readonly number[] makes the compiler reject an in-place sort.
Where does -0 come from, and does it matter?
Negating a zero gives -0, so -nums[i] - nums[j] with two zeros produces -0. === and Set treat it as equal to 0, so the lookup works, but the triplet then prints as [0, -0, 0] in Node. Writing 0 - nums[i] - nums[j] yields a plain 0.
FAQ for Java
Why store List<Integer> in the HashSet instead of int[]?
A HashSet decides what counts as a duplicate through hashCode and equals, and arrays never override the Object versions. Two separate new int[] {-5, 2, 3} arrays are different objects, so a Set<int[]> keeps both and reports size 2. List.of(-5, 2, 3) implements both methods over its elements, so the second add is ignored and the size stays 1. A record Triplet(int a, int b, int c) is another option that also skips boxing, because records generate value-based equals and hashCode from their components.
Does Arrays.sort change the caller's array?
Yes. The method receives a copy of the reference, not of the array, so Arrays.sort(nums) inside threeSum reorders the very object the caller holds. With int[] nums = {3, -1, -2, 5, -3, 0}, sorting nums.clone() gives [-3, -2, -1, 0, 3, 5] and Arrays.toString(nums) is still [3, -1, -2, 5, -3, 0]; pass nums itself to the two-pointer threeSum and it becomes [-3, -2, -1, 0, 3, 5]. Clone inside the method if callers should never notice.
Can the sum of three ints overflow?
It can, and silently: Java int arithmetic wraps around at 2147483647 and -2147483648 without throwing. Take {Integer.MIN_VALUE, Integer.MIN_VALUE, 0}: the true total is -4294967296, the int total wraps to 0, and the two-pointer version reports [[-2147483648, -2147483648, 0]]. Widening one operand, long sum = (long) nums[i] + nums[lo] + nums[hi];, makes it return nothing. If you would rather fail loudly, Math.addExact throws an ArithmeticException on overflow.
How do I find triplets for a target other than 0?
Add an int target parameter and test sum against it: below target advances lo, above it pulls hi back, equal records a match. Delete the nums[i] > 0 break, since a positive first element can still be part of a positive target. With target 2, {3, -1, -2, 5, -3, 0} gives [[-3, 0, 5], [-2, -1, 5], [-1, 0, 3]].
How do I solve 3Sum Closest in Java?
Return one int instead of a list. Sort, run the same lo/hi walk, and keep whichever sum has had the smallest Math.abs(sum - target) so far, returning early on an exact hit. Duplicate skipping can be dropped, because repeats cannot change a single best sum. For {3, -1, -2, 5, -3, 0} with target 10 the result is 8, from 0 + 3 + 5.
FAQ for Go
Why is the map key a [3]int and not a []int?
Go only accepts comparable types as map keys. A [3]int compares all three elements, so two separately built [3]int{-5, 2, 3} values are the same key. A slice is a small header pointing at shared storage and has no ==, so map[[]int]bool{} is a compile error (invalid map key type []int). Pairing the key with struct{}, a value that occupies zero bytes, is the idiomatic way to spell a set in Go.
Will slices.Sort reorder the slice I pass in?
It will. Passing a slice copies only its header, and that header still points at the caller's backing array, so slices.Sort(nums) inside threeSum rearranges the caller's elements. sort.Ints behaves the same way and, since Go 1.22, simply calls slices.Sort. Clone first when that matters: with nums := []int{3, -1, -2, 5, -3, 0}, sorting slices.Clone(nums) yields [-3 -2 -1 0 3 5] while nums still prints [3 -1 -2 5 -3 0].
Is a nil result different from an empty [][]int?
Inside ordinary Go code, no: both have len 0, a range over either does nothing, and fmt.Println shows [] for both. The difference shows up at the JSON boundary, where json.Marshal writes a nil slice as null and [][]int{} as []. If a client parses the response as an array, declare result := [][]int{} instead of var result [][]int.
Can adding three ints overflow in Go?
Not for ordinary input on this engine, where int is 64 bits wide: three values that each fit in 32 bits add up to a few billion at most, far inside the range. The risk comes back if you store the data as []int32 or work near math.MaxInt64, because Go integer addition wraps around silently with no panic. In that case widen to int64 before adding.
How do I solve 3Sum Closest in Go?
The function now returns a single int rather than triplets. After slices.Sort, keep the same lo/hi walk, but compare each sum's distance from the target with the best distance so far and keep the nearer sum; a sum that hits the target exactly can be returned on the spot. math.Abs works on float64, so most Go code adds a tiny abs(x int) int helper. Duplicate skipping can go, since only one number comes back. With []int{3, -1, -2, 5, -3, 0} and target 10, the nearest sum is 8 (0 + 3 + 5).
FAQ for C#
Why store a value tuple in the HashSet instead of an int[]?
A HashSet<T> decides what is a duplicate through GetHashCode and Equals, and arrays never override the reference-based versions from Object. Two separate new[] { -5, 2, 3 } arrays are different objects, so a HashSet<int[]> keeps both and reports Count == 2. The value tuple (-5, 2, 3) is a ValueTuple<int, int, int>, which compares and hashes by its three fields, so the second Add returns false and the count stays 1. A record struct Triplet(int A, int B, int C) does the same with named members, and a string key like $"{a},{b},{c}" works too but allocates on every check.
Does Array.Sort change the caller's array?
Yes. An array is a reference type, so ThreeSum receives a reference to the same object and Array.Sort(nums) reorders it for the caller as well. If that matters, sort a copy: var sorted = (int[]) nums.Clone(); or nums.OrderBy(x => x).ToArray(), and run the two pointers over the copy. The brute-force and hash-set versions never touch the input.
Can the sum of three ints overflow in C#?
By default yes, and silently: int arithmetic wraps at int.MaxValue and int.MinValue unless the project or a checked block asks for an OverflowException. With { int.MinValue, int.MinValue, 0 } the true total is -4294967296 but the int sum wraps to 0 and the triplet is reported. The constraints here keep values within ±10⁸, so three of them fit in an int; for wider ranges compute long sum = (long) nums[i] + nums[lo] + nums[hi]; so the addition happens in 64 bits.
How do I find triplets for a target other than 0?
Add an int target parameter and compare sum with it: below target moves lo right, above it moves hi left, equal records a match. Remove the nums[i] > 0 break, because a positive first value can still be part of a positive target. With target 2, { 3, -1, -2, 5, -3, 0 } gives [-3, 0, 5], [-2, -1, 5] and [-1, 0, 3].
Why return List<int[]>.ToArray() instead of a List<List<int>>?
The signature returns int[][], a jagged array, and the tests compare it element by element. Collecting into a List<int[]> keeps the appends cheap while the count is unknown, and one ToArray() at the end produces the jagged array without copying the inner arrays. For the no-answer case the same call yields an empty int[0][], which is what the tests expect instead of null.
FAQ for C++
Why does set<vector<int>> work but unordered_set<vector<int>> does not compile?
std::set only needs operator<, and vector provides a lexicographic one. unordered_set needs a std::hash specialisation, and the standard library has none for vector<int>, so you would have to write a hash functor. For three ints, set is simpler, or skip the set entirely by sorting first and skipping equal neighbours.
Why write i + 2 < n instead of i < nums.size() - 2?
nums.size() is an unsigned size_t, so on an empty or one-element vector nums.size() - 2 wraps around to a huge number and the loop reads past the end. Casting the size to int once and writing i + 2 < n stays correct for every length.
Does sort change the vector I pass in?
Yes. The parameter is vector<int>&, a reference to the caller's vector, so sort(nums.begin(), nums.end()) reorders it. Take the parameter by value (vector<int> nums) or copy it inside the method if the caller must keep the original order; the copy costs O(n).
Can the sum of three ints overflow?
Signed overflow is undefined behaviour in C++, and three values near INT_MAX exceed it. The constraints keep values within ±10⁸, so the sum stays below 3·10⁸ and fits. For the full int range compute it as long long sum = (long long)nums[i] + nums[lo] + nums[hi];.
Is push_back({a, b, c}) slower than emplace_back?
push_back({a, b, c}) builds a temporary vector<int> from the brace list and moves it in, which is one cheap pointer steal. emplace_back cannot take a bare brace list, so emplace_back(initializer_list<int>{a, b, c}) is longer and no faster. Calling result.reserve(...) is rarely worth it, since the triplet count is unknown up front.
FAQ for C
What are returnSize and returnColumnSizes for?
A pointer does not carry its length, so the caller passes two out-parameters. The function writes the number of triplets to *returnSize and points *returnColumnSizes at a malloc'ed array holding each row's length, here always 3. The caller reads result[r][0..returnColumnSizes[r] - 1] for each r below returnSize, then frees every row, the row array and the sizes array.
Why not write qsort's comparator as return a - b?
Subtracting two ints can overflow, which is undefined behaviour, and on most machines it wraps and flips the sign: comparing INT_MIN with 1 computes INT_MIN - 1, which comes out as a large positive number, so qsort puts the smallest value last. (a > b) - (a < b) gives -1, 0 or 1 for every pair of values and cannot overflow.
How do I grow the result when the triplet count is unknown?
Keep a pointer, a count and a capacity, and when they meet call realloc with double the capacity, as add_triplet does. Doubling makes the total copying O(n) over all appends. Starting from a NULL pointer is fine, since realloc(NULL, size) behaves like malloc(size); production code also checks the return value before overwriting the old pointer.
Why sort a copy instead of the input array?
qsort(nums, ...) would reorder the caller's array, which a caller may not expect from a function that only reads its input. A malloc'ed copy costs O(n) memory and one memcpy, and it is freed before the function returns.
Can the sum of three ints overflow?
With values within ±10⁸ the sum stays below 3·10⁸, well inside int. For the full int range compute it as long long sum = (long long)a[i] + a[lo] + a[hi];, because signed overflow is undefined behaviour in C.
FAQ for Kotlin
Why a HashSet<List<Int>> and not a HashSet<IntArray>?
IntArray is a JVM int[], which keeps the identity-based equals and hashCode from Object. Two separate intArrayOf(-5, 2, 3) are different keys, so a HashSet<IntArray> keeps both. A List<Int> compares element by element, so the second add is ignored. A data class Triplet(val a: Int, val b: Int, val c: Int) works too and avoids boxing.
What is the difference between nums.sort() and nums.sorted()?
nums.sort() sorts the IntArray in place and changes the array the caller passed in. nums.sorted() leaves nums alone and returns a new sorted List<Int>. nums.copyOf().apply { sort() } gives a sorted IntArray copy if you want to stay on primitives.
Why for (i in sorted.indices) and not 0 until sorted.size - 2?
Both are safe in Kotlin: 0 until -1 is an empty range, not an error. Looping over indices is simpler, and the lo < hi check already stops the inner loop for the last two positions.
How do I return a List<List<Int>> instead of Array<IntArray>?
Collect into mutableListOf<List<Int>>() and add listOf(a, b, c) for each match. The workbench signature uses Array<IntArray>, so here the result is converted with toTypedArray() at the end.
Can the sum of three Ints overflow?
Kotlin Int wraps silently past ±2.1 × 10⁹. The constraints keep values within ±10⁸, so three of them stay far inside the range. For wider input, widen one operand: sorted[i].toLong() + sorted[lo] + sorted[hi].
FAQ for Rust
Why mut nums in the parameter list?
The function receives the Vec<i32> by value, so it owns it and the caller can no longer see it. Writing mut nums makes that owned binding mutable, which sort_unstable needs. No copy is made; with &[i32] you would have to clone with nums.to_vec() before sorting.
Why does for i in 0..nums.len() - 2 panic on short input?
nums.len() is a usize, and 0 - 2 underflows, which panics in a debug build ("attempt to subtract with overflow"). Use nums.len().saturating_sub(2) or loop over the whole range and let lo < hi do the work, as the solution does. nums.len() - 1 for hi is safe there because the loop only runs when nums is not empty.
Why a HashSet<[i32; 3]> instead of HashSet<Vec<i32>>?
Both work: arrays and vectors hash and compare by value. A [i32; 3] lives on the stack with no allocation per triplet, and its size is part of the type, so it cannot hold the wrong number of values. to_vec() turns each one into the Vec<i32> the signature needs.
Why sort_unstable and not sort?
sort_unstable does not keep equal elements in their original order, which is meaningless for plain integers anyway, and it is usually faster and allocates nothing. sort is a stable merge sort that allocates a buffer; both give the same result here.
Can nums[i] + nums[lo] + nums[hi] overflow?
In a debug build an i32 overflow panics, in release it wraps. The constraints keep values within ±10⁸, so the sum stays below 3 × 10⁸. For the full i32 range, add as i64: nums[i] as i64 + nums[lo] as i64 + nums[hi] as i64.
FAQ for Swift
Why does for i in 0..<nums.count - 2 crash on a short array?
With fewer than two elements the upper bound is negative, and building a range whose lower bound is above its upper bound traps at runtime ("Range requires lowerBound <= upperBound"). Looping over nums.indices avoids it; the lo < hi check already skips the last two positions.
Can I sort nums in place?
Not directly: function parameters are let constants, so nums.sort() does not compile. let nums = nums.sorted() makes a sorted copy under the same name, or var nums = nums followed by nums.sort(). Arrays are value types, so neither changes the caller's array.
Why can a Set hold [Int] in Swift?
Since Swift 4.2 an Array conforms to Hashable whenever its Element does. [-5, 2, 3] built twice hashes and compares equal, so Set<[Int]> removes the duplicate. A small struct Triplet: Hashable { let a, b, c: Int } works too and gets its conformance synthesized.
Why does the order of the triplets change between runs?
Swift seeds its hashing randomly per process, so Array(found) lists the set in a different order each run. The triplets can come in any order here; call .sorted { $0.lexicographicallyPrecedes($1) } if you want a stable listing.
Can the sum overflow?
Int is 64-bit on current platforms, and Swift traps on overflow instead of wrapping. With values within ±10⁸ three of them are nowhere near the limit. The &+ operator wraps silently if you ever need it.
FAQ for PHP
Does sort($nums) change the caller's array?
No. PHP passes arrays by value (copy-on-write), so sort inside the method works on the method's own copy. Only a by-reference parameter, function threeSum(array &$nums), would let the sort reach the caller.
Why use implode as the key for the brute force?
PHP array keys can only be integers or strings, so an array like [-5, 2, 3] cannot be a key itself. implode(',', $t) turns the sorted triplet into the string "-5,2,3", which is the same for every copy of that triplet. in_array($t, $found) would also find duplicates, but it scans the whole list on every match.
Why return array_values($found)?
$found is keyed by strings such as "-5,2,3", so json_encode would print it as an object, not a list. array_values renumbers it from 0, giving the int[][] list the signature expects.
Is sort() enough for negative numbers?
Yes. With integer values sort uses numeric comparison and orders [3, -1, -2, 5, -3, 0] as [-3, -2, -1, 0, 3, 5]. It also renumbers the keys from 0, which the index arithmetic relies on. Pass SORT_NUMERIC if the input could contain numeric strings.
Can the sum overflow?
PHP integers are 64-bit on current builds, and a sum past PHP_INT_MAX becomes a float rather than wrapping. With values within ±10⁸ the sum of three is nowhere near that, so === 0 compares two integers.
FAQ for Ruby
Why can a Set hold arrays and still spot duplicates?
Set is built on Hash, which compares keys with eql? and hash. Array defines both over its elements, so [-5, 2, 3] built twice counts as one entry. Sort each triplet first: [2, -5, 3] and [-5, 2, 3] are different arrays.
What is the difference between sort and sort!?
nums.sort returns a new sorted array and leaves nums alone. nums.sort! sorts in place and changes the array the caller passed in. Writing nums = nums.sort rebinds the local name to the copy, which is the safe choice inside a method.
Could combination(3) replace the three loops?
nums.combination(3).select { |t| t.sum.zero? }.map(&:sort).uniq is a one-line brute force. It builds a new array for every triple, about 4.5 million at the size bound, so it is noticeably slower than index loops, but it is still O(n³) and fine for small inputs.
Do I need require 'set'?
From Ruby 3.2 Set is loaded automatically; on older versions Set.new raises NameError without the require. Keeping the line is harmless. A Hash with the sorted triplet as the key, found[t] = true and found.keys, works the same way without it.
Does break inside each_with_index leave the method?
No. break in a block ends the each_with_index call, and the method carries on to result. next skips to the next element, like continue elsewhere. Only return would leave the method itself.
FAQ for Dart
Why not a Set<List<int>> to remove duplicate triplets?
Dart List uses identity for == and hashCode, so [-5, 2, 3] == [-5, 2, 3] is false and a Set<List<int>> keeps both. A string key such as t.join(',') compares by value. Records do too: (int, int, int) has structural equality since Dart 3, so a Set<(int, int, int)> works as well.
Does sort() change the caller's list?
Yes, List.sort sorts in place and returns void. That is why the code copies first with the spread [...nums] and uses the cascade ..sort(), which sorts the copy and still evaluates to the list. nums.sort() on its own would reorder the argument.
Why ..sort() and not .sort()?
The cascade operator .. calls a method and returns the receiver instead of the method's result. [a, b, c].sort() evaluates to void, so it cannot be assigned; [a, b, c]..sort() evaluates to the sorted list.
Is i < sorted.length - 2 safe for an empty list?
Yes. Dart int is signed, so 0 - 2 is just -2 and the loop does not run. In languages with unsigned lengths the same expression underflows, which is why it is worth checking.
Can the sum overflow?
On the Dart VM int is 64-bit, so three values within ±10⁸ are far from the limit. Compiled to JavaScript, integers are exact up to 2⁵³, which is still plenty here.
FAQ for Scala
Why a HashSet[List[Int]] and not a HashSet[Array[Int]]?
A Scala Array is a JVM array, so == and hashCode are identity based: two separate Array(-5, 2, 3) are different set entries. List, Vector and tuples compare by their elements, so List(-5, 2, 3) added twice is stored once. A tuple (a, b, c) is another value-equal key.
Why while loops instead of break and continue?
Scala has no break or continue keywords. The two-pointer loop folds the early exit into the while condition (s(i) <= 0) and the duplicate skip into an if. scala.util.boundary with break(value) is the Scala 3 way to leave a block early; a return inside a for body would be a non-local return, which Scala 3 warns about.
Does nums.sorted change the input array?
No. sorted returns a new Array[Int], so the caller's array keeps its order. To sort in place, use scala.util.Sorting.quickSort(nums) or java.util.Arrays.sort(nums), both of which change the array they are given.
Is the for comprehension with three generators slow?
It desugars into nested foreach calls with closures over Ranges, and the guard into withFilter. On the JVM that is a little slower than while loops but still O(n³) with a small constant; at the size bound it finishes in well under a second.
Can the sum overflow?
An Int wraps silently past ±2.1 × 10⁹. The constraints keep values within ±10⁸, so the sum of three fits. For wider input, widen one operand: s(i).toLong + s(lo) + s(hi).