Leetcode 15: 3 Sum

May 17, 2016

problem statement:

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

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.

Julia likes to write some code after she reads the blog:

http://www.cnblogs.com/TenosDoIt/p/3649607.html

Write her own practice using C#: 

https://gist.github.com/jianminchen/9ca3f9982c1011ed4a658f83ca203549

https://github.com/jianminchen/Leetcode_C-/blob/master/15_3Sum.cs

Pass Leetcode online Judge

Line 62, Change the variable name from newTarget to twoSumTarget, since newTarget is not so clear, confusing. 

https://gist.github.com/jianminchen/61c848a30b1e10364359d2d73c0338fe

Question and Answer:

1. How is your practice?

Answer: Julia tried to practice guidelines from "Clean Code", she learned a few things:
name a list variable to avoid using "list", HashSet variable does not call "set", force her to think about meaningful name. 
For example, line 47 - keys, variable is declared as HashSet<string>. 

 1.  She tried to put "two sum target" function (line 62 - line 103) as a while loop instead of standalone function; 

 2.  Confused with target - 3 sum target with 2 sum target, two variables - naming change:

     newTarget -> twoSumTarget (line 62)

 3. 3 variables are replaced by an array: line 58, trialTriplet

 4. line 71 twoSumValue variable is named to explicitly tell the sum of 2 values, not 3 values.

2. Fun time?

2.1 Julia spent more than 45 minutes to go over C# Array class and all API,

Array.Sum(), use C# Array.Sum() instead of writing yourself.

2.2. 3 variables related to target value, 

target, twoSumTarget, twoSumValue

Good time to read the blog: (10 - 20 minutes)

http://www.sigmainfy.com/blog/summary-of-ksum-problems.html

3. Can you improve the code to get rid of using HashSet to check duplicate? 
Answer: 
Read the blog: 
http://fisherlei.blogspot.ca/2013/01/leetcode-3-sum-solution.html 

line 21, 22: quick solution to avoid duplicate set: 

while(start<end && num[start] == num[start-1]) start++;   

while(start<end && num[end] == num[end+1]) end--;