3Sum 2 Different implementations complexity
Your version

You have a bug in your three-loop implementation. This sort of bug creeps in when you use copy/paste to code without being diligent about checking what's useful. In your 'k' loop you have:


for (int k = i + 2; k &lt; array.Count ; k++)



But that should loop from j + 1 and not i + 1. You should have:

for (int k = j + 1; k &lt; array.Count ; k++)


This will significantly improve your performance for large lists.

The performance of this option will scale in terms of \$O(n^3)\$ which means each time you double the input data size, you will take 8 times longer to compute a result.

Wiki Version

The second method uses the wiki algorithm, which is also the base of the algorithm I would recommend....

The Sort will take \$O(n \log{n})\$ time. For largeish lists the log(n) can be effectively ignored....

What's interesting here, is that you loop to the array size still in the i loop. You can actually limit the outer loop to valeus less than or equal to 0.

At least one of the values has to be 0 or less in order for there to be a zero-sum.

Similarly, once you have a second number, chosen from values after i, you should then be able to do a binary-search for the third number.