In the scenario I present to you, my solution is supposed to represent O(n^2*对数n), and the "pointers" solution, which I assume is the fastest way to resolve the "3SUM" problem, represents O(n^2 * 1); leaving the question of is O(1) faster than O(log n), exampling it with my code.
Could someone explain why this seems to be the case? Please. My logic tells me that O(log n) should be as fast as O(1), if not faster.
I hope my comments on the code of my solution are clear.
Edit:我知道这听起来不太明智…log(n)计算输入(n->;∞), 虽然1…只是1.但是,在这种情况下,对于查找数字,如何更快地进行求和和和减法,而不是使用二进制搜索(log n)?它只是没有进入我的脑海.
LeetCode 3SUM问题描述
O(n^2*对数n)
对于3000个值的输入:
- 迭代次数:
1,722,085 (61% less than the "pointers solution")- 运行时间:~92 ms (270% slower than the typical O(n^2) solution)
public IList<IList<int>> MySolution(int[] nums)
{
IList<IList<int>> triplets = new List<IList<int>>();
Array.Sort(nums);
for (int i = 0; i < nums.Length; i++)
{
// Avoid duplicating results.
if (i > 0 && nums[i] == nums[i - 1])
continue;
for (int j = i+1; j < nums.Length - 1; j++)
{
// Avoid duplicating results.
if (j > (i+1) && nums[j] == nums[j - 1])
continue;
// The solution for this triplet.
int numK = -(nums[i] + nums[j]);
// * This is the problem.
// Search for 'k' index in the array.
int kSearch = Array.BinarySearch(nums, j + 1, nums.Length - (j + 1), numK);
// 'numK' exists in the array.
if (kSearch > 0)
{
triplets.Add(new List<int>() { nums[i], nums[j], numK });
}
// 'numK' is too small, break this loop since its value is just going to increase.
else if (~kSearch == (j + 1))
{
break;
}
}
}
return triplets;
}
O(n^2)
对于3000个值的相同输入:
- 迭代次数:4.458.579
- 运行时间:~34 ms
public IList<IList<int>> PointersSolution(int[] nums)
{
IList<IList<int>> triplets = new List<IList<int>>();
Array.Sort(nums);
for (int i = 0; i < nums.Length; i++)
{
if (i > 0 && nums[i] == nums[i - 1])
continue;
int l = i + 1, r = nums.Length - 1;
while (l < r)
{
int sum = nums[i] + nums[l] + nums[r];
if (sum < 0)
{
l++;
}
else if (sum > 0)
{
r--;
}
else
{
triplets.Add(new List<int>() { nums[i], nums[l], nums[r] });
do
{
l++;
}
while (l < r && nums[l] == nums[l - 1]);
}
}
}
return triplets;
}