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.
- The solution set must not contain duplicate triplets.
Example:
- Given array S = [-1, 0, 1, 2, -1, -4],
- A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
C Solution:
/**
* Return an array of arrays of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
void sort(int *nums, int numsSize) {
if (numsSize < 2) return;
int key = nums[numsSize - 1];
int i;
for (i = 0; i < numsSize - 1 && nums[i] < key; i++);
if (i == numsSize - 1) {
sort(nums, numsSize - 1);
return;
}
int j;
for (j = i + 1; j < numsSize - 1; j++) {
if (nums[j] < key) {
nums[j] ^= nums[i];
nums[i] ^= nums[j];
nums[j] ^= nums[i++];
}
}
nums[numsSize - 1] = nums[i];
nums[i] = key;
sort(nums, i);
sort(nums + i + 1, numsSize - i - 1);
}
void save(int ***res, int *size, int *returnSize, int n1, int n2, int n3) {
if (*size == *returnSize) {
*size += 1000;
*res = realloc(*res, *size * sizeof(int *));
}
int *tmp = malloc(3 * sizeof(int));
tmp[0] = n1;
tmp[1] = n2;
tmp[2] = n3;
(*res)[(*returnSize)++] = tmp;
}
void twoSum(int *nums, int numsSize, int target, int ***res, int *size, int *returnSize) {
int *l, *r;
for (l = nums, r = nums + numsSize - 1; l < r; ) {
if (*l + *r == target) {
save(res, size, returnSize, -target, *l, *r);
for (l++; l < r && *(l - 1) == *l; l++);
for (r--; l < r && *r == *(r + 1); r--);
}
else if (*l + *r < target) {
for (l++; l < r && *(l - 1) == *l; l++);
}
else {
for (r--; l < r && *r == *(r + 1); r--);
}
}
}
int** threeSum(int* nums, int numsSize, int* returnSize) {
sort(nums, numsSize);
int size = 1000;
int **res = malloc(size * sizeof(int *));
*returnSize = 0;
int i;
for (i = 0; i < numsSize - 2;) {
twoSum(nums + i + 1, numsSize - i - 1, -nums[i], &res, &size, returnSize);
for (i++; i < numsSize - 2 && nums[i - 1] == nums[i]; i++);
}
return res;
}
Python Solution:
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
res = []
i = 0
while i < len(nums) - 2:
l, r = i + 1, len(nums) - 1
while l < r:
sum = nums[i] + nums[l] + nums[r]
if not sum:
res.append([nums[i], nums[l], nums[r]])
if sum > 0:
r -= 1
while r > l and nums[r] == nums[r + 1]:
r -= 1
else:
l += 1
while l < r and nums[l] == nums[l - 1]:
l += 1
i += 1
while i < len(nums) - 2 and nums[i] == nums[i - 1]:
i += 1
return res
Summary:
- For twoSum, the complexity of sort is O(NlgN), so HashTable whose complexity is O(N) is a better solution.
- But for threeSum, the complexity is at least O(N2), in this case sort is acceptable.
- The solution set must not contain duplicate triplets, this reqirement make sort more than necessary.
- 19ms, beat 88.97%.
LeetCode: 15. 3Sum
近期评论