Tuesday, May 17, 2016

Leetcode 15: 3 Sum

May 17, 2016


problem statement:
https://leetcode.com/problems/3sum/
Given an array S of n integers, are there elements abc 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:


Write her own practice using C#: 

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

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)

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--; 




No comments:

Post a Comment