find 3 numbers in one array [1...n] to make a+b=c. By by O(n^2).
sort the array first to get nums[], then
int threeSUM(int *nums, int size)
{
int i, j, k, result;
for (i = 0; i < size; i++)
{
j = 0;
k = size - 1;
while ( j < k )
{
result = nums[j] + nums[k] - nums[i];
if ((result < 0) || (i == j))
j++;
else if ((result > 0) || (i == k))
k--;
else
return 1;
}
}
return 0;
}
No comments:
Post a Comment