Leetcode 15: 3 sum ( II)

Dec. 26, 2016

Problem statement:
https://leetcode.com/problems/3sum/

Review the algorithm:

Previous work:
http://juliachencoding.blogspot.ca/2016/05/leetcode-17-3-sum.html

Array.BinarySearch

Code review:
http://codereview.stackexchange.com/questions/37922/given-an-array-find-any-three-numbers-which-sum-to-zero?rq=1

The idea used in the above code review, time complexity is O(n*n*logn), time limit exceed.

Here is C# written by Julia:

https://gist.github.com/jianminchen/d483ccbc33940bc51cab7996e94a4950

Highlights of improvement:

1. Use Array.ToList() API;  2. Write a function PrepareKey()
https://gist.github.com/jianminchen/d17ad71a561193984e75ab4e7fb91073

2. Comment out the statement:
//int[] searchArray = nums.Skip(j + 1).ToArray();  // O(n) -> make algorithm O(n*n*n)
https://gist.github.com/jianminchen/cbc62795cc5eca621c395a7a5dc3f6bd

Two pointers technique 

Best solution is to use two pointers, therefore, time complexity is O(n*n) instead.

May, 2016
http://juliachencoding.blogspot.ca/2016/05/leetcode-17-3-sum.html

Code review and improve C# implementation on Dec. 26, 2016:
https://gist.github.com/jianminchen/9c62e27297ff94052320160b6967a61c

Stackexchange.com code review link:
http://codereview.stackexchange.com/q/150920/123986

Good news! win Best Question badge (over 10 up-votes) on stackexchange.com, gain 55 reputation on this 3 sum question. Less than 24 hours after publishing.

Two versions of code from code review:
1. From the code review:
http://codereview.stackexchange.com/a/150938/123986
C# code:
https://gist.github.com/jianminchen/dfebe273c5beca0fbbb52981f3934ded

2. From code review:
http://codereview.stackexchange.com/a/150952/123986

C# code:
https://gist.github.com/jianminchen/9ba704a49e740abad0cef99b4d760b69