Commitdb156a6

committed

add 15.3sum

1 parentf8bddb2 commitdb156a6Copy full SHA for db156a6

File tree

+40

-0

lines changed

+40

-0

lines changed

Lines changed: 39 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,39 @@`
	`1`	`+/**`
	`2`	`+ * Key: first pointer tracks from the first element to the last third element.`
	`3`	`+ * then, it is a 2sum problem for finding -nums[i] from the remaining elements.`
	`4`	`+ * no matter which pointer meets a duplicate, just skip the duplicate.`
	`5`	`+ *`
	`6`	`+ *@param {number[]} nums`
	`7`	`+ *@return {number[][]}`
	`8`	`+ */`
	`9`	`+varthreeSum=function(nums){`
	`10`	`+nums.sort(function(a,b){`
	`11`	`+returna-b;`
	`12`	`+});`
	`13`	`+`
	`14`	`+varresults=[];`
	`15`	`+`
	`16`	`+for(vari=0;i<nums.length-2;i++){`
	`17`	`+// there is a same number, because this number has been checked last time, skip it.`
	`18`	`+if(i>0&&nums[i]===nums[i-1])continue;`
	`19`	`+varlo=i+1;`
	`20`	`+varhi=nums.length-1;`
	`21`	`+vartwoSum=0-nums[i];`
	`22`	`+while(lo<hi){`
	`23`	`+if(nums[lo]+nums[hi]===twoSum){`
	`24`	`+results.push([nums[i],nums[lo],nums[hi]]);`
	`25`	`+// there is a same number, because this number has been checked last time, skip it.`
	`26`	`+while(lo<hi&&nums[lo]===nums[lo+1])lo++;`
	`27`	`+while(lo<hi&&nums[hi]===nums[hi-1])hi--;`
	`28`	`+lo++;`
	`29`	`+hi--;`
	`30`	`+}elseif(nums[lo]+nums[hi]<twoSum){`
	`31`	`+lo++;`
	`32`	`+}else{`
	`33`	`+hi--;`
	`34`	`+}`
	`35`	`+}`
	`36`	`+}`
	`37`	`+`
	`38`	`+returnresults;`
	`39`	`+};`

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -66,6 +66,7 @@`
`66`	`66`	`*[1. Two Sum](https://leetcode.com/problems/two-sum/) -[Solution](./Medium/1-twoSum.js)`
`67`	`67`	`*[3. Longest Substring Without Repeating Characters](https://oj.leetcode.com/problems/longest-substring-without-repeating-characters/) -[Solution](./Medium/3-lengthOfLongestSubstring.js)`
`68`	`68`	`*[11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/) -[Solution](./Medium/11-containerMostWater.js)`
	`69`	`+*[15. 3Sum](https://leetcode.com/problems/3sum/) -[Solution](./Medium/15-3sum.js)`
`69`	`70`	`*[22. Generate Parentheses](https://leetcode.com/problems/generate-parentheses/) -[Solution](./Medium/22-generateParentheses.js)`
`70`	`71`	`*[24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/) -[Solution](./Medium/24-swapNodesPairs.js)`
`71`	`72`	`*[35. Search Insert Position Characters](https://oj.leetcode.com/problems/search-insert-position/) -[Solution](./Medium/35-searchInsert.js)`

Comments

(0)