Commit885b065

committed

MEDIUM/src/medium/_3Sum_Smaller.java

1 parentbb55054 commit885b065Copy full SHA for 885b065

File tree

+42

-0

lines changed

+42

-0

lines changed

Lines changed: 42 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,42 @@`
	`1`	`+packagemedium;`
	`2`	`+`
	`3`	`+importjava.util.Arrays;`
	`4`	`+`
	`5`	`+/**259. 3Sum Smaller`
	`6`	`+`
	`7`	`+ Total Accepted: 13428`
	`8`	`+ Total Submissions: 33743`
	`9`	`+ Difficulty: Medium`
	`10`	`+`
	`11`	`+Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.`
	`12`	`+`
	`13`	`+For example, given nums = [-2, 0, 1, 3], and target = 2.`
	`14`	`+`
	`15`	`+Return 2. Because there are two triplets which sums are less than 2:`
	`16`	`+`
	`17`	`+[-2, 0, 1]`
	`18`	`+[-2, 0, 3]`
	`19`	`+`
	`20`	`+Follow up:`
	`21`	`+Could you solve it in O(n2) runtime? */`
	`22`	`+publicclass_3Sum_Smaller {`
	`23`	`+`
	`24`	`+/*Basically, very similar to 3Sum, but the key is that you'll have to add result by (right-left), not just increment result by 1!/`
	`25`	`+publicintthreeSumSmaller(int[]nums,inttarget) {`
	`26`	`+if(nums ==null \|\|nums.length ==0)return0;`
	`27`	`+intresult =0;`
	`28`	`+Arrays.sort(nums);`
	`29`	`+for(inti =0;i <nums.length-2;i++){`
	`30`	`+intleft =i+1,right =nums.length-1;`
	`31`	`+while(left <right){`
	`32`	`+intsum =nums[i] +nums[left] +nums[right];`
	`33`	`+if(sum <target) {`
	`34`	`+result +=right-left;//this line is super cool!`
	`35`	`+left++;`
	`36`	`+ }elseright--;`
	`37`	`+ }`
	`38`	`+ }`
	`39`	`+returnresult;`
	`40`	`+ }`
	`41`	`+`
	`42`	`+}`

Comments

(0)