Solve 3Sum: find all unique triplets that sum to zero.
#include <stdio.h>
#include <stdlib.h>
static int cmp_int(const void *a, const void *b)
{
int x = *(const int *)a, y = *(const int *)b;
return (x > y) - (x < y);
}
void three_sum(int *a, size_t n)
{
qsort(a, n, sizeof *a, cmp_int);
for (size_t i = 0; i + 2 < n; i++) {
if (i > 0 && a[i] == a[i - 1]) continue; /* skip duplicate first values */
size_t l = i + 1, r = n - 1;
while (l < r) {
long sum = (long)a[i] + a[l] + a[r];
if (sum < 0) l++;
else if (sum > 0) r--;
else {
printf("[%d, %d, %d]\n", a[i], a[l], a[r]);
while (l < r && a[l] == a[l + 1]) l++; /* skip duplicates */
while (l < r && a[r] == a[r - 1]) r--;
l++; r--;
}
}
}
}
/* {-1, 0, 1, 2, -1, -4} -> [-1, -1, 2] and [-1, 0, 1] */
Points: sort, fix the first element, then two pointers on the rest: O(n²) time, O(1) extra space; skip equal values to avoid duplicate triplets.