Skip to main content

Posts

Showing posts from April, 2018

Another solution for 3SUM problem

The 3SUM problem asks if a given set of n real numbers contains three elements that sum to zero.

It is a bit different solution comparing to known ones, time complexity is O(k2 + m2) where k + m <= n; what actually is the same as O(n2) but the solution is rather fast (beats 92.97% C# and 97.98% Python solutions on LeetCode).

The solution is based on the idea that in order to get zero sum we need at least one positive and one negative number. We can split the input into 2 sets, for positive and negative numbers. Zeros affect the output in the following way: 1 zero gives ability to combine triplets of positive number + negative number + zero; 3 and more zeros gives one additional result: a triplet consisting of zeros only. 
C# solution:using System; using System.Collections.Generic; class Solution { public IList<IList<int>> ThreeSum(int[] nums) { var result = new List<IList<int>>(); int negativeEnd = -1; int positiveStart = -1…