1. Description

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

2. Example

given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

3. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

static int compare(const void* a, const void *b) {
	return *(int*)a - *(int*)b;
}

int** threeSum(int* nums, int numsSize, int* returnSize) {
	qsort(nums, numsSize, sizeof(int), compare);

	int ** result = malloc(numsSize * numsSize * sizeof(int *) / 2);

	int target, head, tail; *returnSize = 0;

	for (int i = 0; i < numsSize - 2; i++)
	{
		if (i > 0 && nums[i] == nums[i-1])
		{
			continue;
		}

		target = -nums[i]; head = i + 1; tail = numsSize - 1;

		while (head < tail) 
		{
			while (head < tail && nums[head] + nums[tail] < target) head++;
			while (head < tail && nums[head] + nums[tail] > target) tail--;

			if (head >= tail || nums[head] + nums[tail] != target)
			{
				continue;
			}

			result[*returnSize] = (int*)malloc(3 * sizeof(int));
			result[*returnSize][0] = nums[i];
			result[*returnSize][1] = nums[head];
			result[(*returnSize)++][2] = nums[tail];

			while (head < tail && nums[head] == nums[head + 1]) head++;
			while (head < tail && nums[tail] == nums[tail - 1]) tail--;

			head++;
			tail--;
		}
	}
	return result;
}

[/restab]
[/restabs]

4.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

#include

static int compare(const void* a, const void *b) {
	return *(int*)a - *(int*)b;
}

int** threeSum(int* nums, int numsSize, int* returnSize) {
	qsort(nums, numsSize, sizeof(int), compare);

	int ** result = malloc(numsSize * numsSize * sizeof(int *) / 2);

	int target, head, tail; *returnSize = 0;

	for (int i = 0; i < numsSize - 2; i++)
	{
		if (i > 0 && nums[i] == nums[i-1])
		{
			continue;
		}

		target = -nums[i]; head = i + 1; tail = numsSize - 1;

		while (head < tail) 
		{
			while (head < tail && nums[head] + nums[tail] < target) head++;
			while (head < tail && nums[head] + nums[tail] > target) tail--;

			if (head >= tail || nums[head] + nums[tail] != target)
			{
				continue;
			}

			result[*returnSize] = (int*)malloc(3 * sizeof(int));
			result[*returnSize][0] = nums[i];
			result[*returnSize][1] = nums[head];
			result[(*returnSize)++][2] = nums[tail];

			while (head < tail && nums[head] == nums[head + 1]) head++;
			while (head < tail && nums[tail] == nums[tail - 1]) tail--;

			head++;
			tail--;
		}
	}
	return result;
}

int main()
{
	int arr[] = { -2, 0, 0, 2, 2 };
	int **res = NULL;
	int size;

	res = threeSum(arr, 5, &size);

	for (int i = 0; i < size; i++)
	{
		printf("(%d, %d, %d)\n", res[i][0], res[i][1], res[i][2]);
	}

	for (int i = 0; i < size; i++)
	{
		free(res[i]);
	}
	free(res);
	system("pause");
	return 0;
}

[/restab]
[/restabs]

5. Submission Details

6. Runtime Distribution