Created
December 27, 2016 05:03
-
-
Save jianminchen/d17ad71a561193984e75ab4e7fb91073 to your computer and use it in GitHub Desktop.
Leetcode 15 - 3 sum - binary search - improve the code
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
namespace _16_3Sum | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
ThreeSumTestCase(); | |
} | |
private static void ThreeSumTestCase() | |
{ | |
// test 3 sum closest | |
int[] arr = new int[6] { -1, 0, 1, 2, -1, -4 }; | |
IList<IList<int>> triplets = ThreeSum(arr); | |
} | |
/* | |
* Dec. 26, 2016 | |
* http://codereview.stackexchange.com/questions/37922/given-an-array-find-any-three-numbers-which-sum-to-zero?rq=1 | |
* | |
* May 17, 2016 | |
* Work on this 3 sum close algorithm | |
* | |
* Given an array S of n integers, are there elements a, b, c in S | |
* such that a + b + c = 0? Find all unique triplets in the array | |
* which gives the sum of zero. | |
Note: | |
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) | |
The solution set must not contain duplicate triplets. | |
* | |
For example, given array S = {-1 0 1 2 -1 -4}, | |
A solution set is: | |
(-1, 0, 1) | |
(-1, -1, 2) | |
* | |
* TLE - time limited exceeded | |
* O(n*n*logn) | |
* | |
* Best time complexity using two points - O(n*n) | |
* | |
* | |
* | |
*/ | |
public static IList<IList<int>> ThreeSum(int[] nums) | |
{ | |
IList<IList<int>> triplets = new List<IList<int>>(); | |
HashSet<string> foundNos = new HashSet<string>(); | |
if (nums == null || nums.Length == 0) | |
return triplets; | |
Array.Sort(nums); | |
int len = nums.Length; | |
for (int i = 0; i < len - 2; i++) // len = 3, test case passes! | |
{ | |
for(int j = i+1; j < len; j++) | |
{ | |
int[] searchArray = nums.Skip(j + 1).ToArray(); | |
int searchValue = -1 * (nums[i] + nums[j]); | |
int index = Array.BinarySearch(searchArray, searchValue); | |
if (index >= 0) | |
{ | |
int[] numberAsc = new int[] { nums[i], nums[j], searchArray[index] }; | |
string key = PrepareKey(numberAsc, ','); | |
if (foundNos.Contains(key)) | |
continue; | |
foundNos.Add(key); | |
IList<int> threeNos = numberAsc.ToList(); | |
triplets.Add(threeNos); | |
} | |
} | |
} | |
return triplets; | |
} | |
/* | |
* | |
*/ | |
private static string PrepareKey(int[] numbers, char delimiter) | |
{ | |
if(numbers == null || numbers.Length == 0) | |
return ""; | |
string key = string.Empty; | |
for (int i = 0; i < numbers.Length; i++ ) | |
{ | |
key += numbers[i] + delimiter.ToString(); | |
} | |
return key; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment