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(k

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.

It is a bit different solution comparing to known ones, time complexity is O(k

^{2}+ m^{2}) where k + m <= n; what actually is the same as O(n^{2}) 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; Array.Sort(nums); //hash containing negative numbers var negativeHash = new HashSet<int>(); //hash containing positive numbers var positiveHash = new HashSet<int>(); for (int i = 0; i < nums.Length; i++) { var item = nums[i]; if (item > 0) { if (positiveStart == -1) { positiveStart = i; for (; i < nums.Length; i++) positiveHash.Add(nums[i]); } } else if (item < 0) { negativeEnd = i; negativeHash.Add(item); } } var zerosCount = (positiveStart != -1 ? positiveStart : nums.Length) - negativeEnd - 1; //check if the result completed from zeros only is possible if (zerosCount > 2) result.Add(new[] { 0, 0, 0 }); //if either negative or positive numbers are absent is it not possible to create any combinations if (negativeEnd == -1 || positiveStart == -1) return result; //check if sum of 2 negative numbers has complementary positive number CheckThree(ref nums, 0, negativeEnd, ref positiveHash, ref result); //check if sum of 2 positive numbers has complementary negative number CheckThree(ref nums, positiveStart, nums.Length - 1, ref negativeHash, ref result); //check if there are pairs of complementary negative and positive numbers if (zerosCount > 0) CheckTwo(ref positiveHash, ref negativeHash, ref result); return result; } private void CheckTwo(ref HashSet<int> positiveHash, ref HashSet<int> negativeHash, ref List<IList<int>> result) { foreach (var item in positiveHash) { var checkedItem = -item; if (negativeHash.Contains(checkedItem)) result.Add(new[] { item, 0, checkedItem }); } } private void CheckThree(ref int[] nums, int start, int end, ref HashSet<int> opposite, ref List<IList<int>> result) { for (var i = start; i < end; i++) { var a = nums[i]; if (i == start || a != nums[i - 1]) { var jStart = i + 1; for (var j = jStart; j <= end; j++) { var b = nums[j]; if (j == jStart || b != nums[j - 1]) { var c = -a - b; if (opposite.Contains(c)) { result.Add(new[] { a, b, c }); } } } } } } }

**Python solution**

class Solution(object): def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ nums.sort() self._result = list() self._nums = nums negativeEnd = -1 positiveStart = -1 length = len(nums) negativeHash = set() positiveHash = set() for i,item in enumerate(nums): if item > 0: if positiveStart == -1: positiveStart = i positiveHash = set(nums[i:length]) elif item < 0: negativeEnd = i negativeHash.add(item) zeroCount = (positiveStart if positiveStart != -1 else length) - negativeEnd - 1 #check if the result completed from zeros only is possible if zeroCount > 2: self._result.append([0, 0, 0]) #if either negative or positive numbers are absent is it not possible to create any combinations if negativeEnd == -1 or positiveStart == -1: return self._result #check if sum of 2 negative numbers has complementary positive number self._check3(0, negativeEnd, positiveHash) #check if sum of 2 positive numbers has complementary negative number self._check3(positiveStart, length-1, negativeHash) #check if there are pairs of complementary negative and positive numbers if zeroCount > 0: self._check2(positiveHash, negativeHash) return self._result def _check2(self, positiveHash, negativeHash): for item in positiveHash: checked = -item if checked in negativeHash: self._result.append([item, 0, checked]) def _check3(self, start, end, opposite): slice1 = self._nums[start:end+1] for i, a in enumerate(slice1): if i == 0 or a != slice1[i-1]: slice2 = slice1[i + 1:] for j, b in enumerate(slice2): if j == 0 or b != slice2[j - 1]: c = -a -b if c in opposite: self._result.append([a, b, c])

## Comments

## Post a Comment