微博：http://www.weibo.com/cathyhwzn
刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions
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
for example, input [-2, -1, 0, 2, 1], output [[-2, 0, 2], [-1, 0, 1] ].
If we have worked on 2 sum before, then it won't be too hard for us to work this out. However, it's a long way to go from getting the idea of solving the problem, design the problem and make the code right.
In the 3sum, we use two pointers and a loop. The loop iterate through the whole array and the two pointers point to the elements in the left and right side of the num[k]. To see whether num[i]+num[k]+num[j] = 0 or not. We sort the array first. The key point here, we need to set two check variables to avoid the duplicate results.
Is not good. can not pass the larger judge
ReplyDeleteThis is not my code...as you may notice I only use C++ as my language. And this code (is Java ) shows correct idea of how to use pointers iterate through the array, so I use it(because of laziness....) And I have used my own code on oj (sure it passed). If you need, I can paste my own code here.
Delete