Created
December 27, 2016 04:42
-
-
Save jianminchen/d483ccbc33940bc51cab7996e94a4950 to your computer and use it in GitHub Desktop.
Leetcode 15 - 3 sum - using binary search, code review: http://codereview.stackexchange.com/a/38208/123986, Leetcode online judge: TLE
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 = numberAsc[0] + "," + numberAsc[1] + "," + numberAsc[2]; | |
if (foundNos.Contains(key)) | |
continue; | |
foundNos.Add(key); | |
IList<int> threeNos = new List<int>(); | |
threeNos.Add(numberAsc[0]); | |
threeNos.Add(numberAsc[1]); | |
threeNos.Add(numberAsc[2]); | |
triplets.Add(threeNos); | |
} | |
} | |
} | |
return triplets; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment