Monday, April 28, 2008

3 sum problem 3sum

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