[LeetCode]15. 3Sum(Medium)
Description:
Given an array
numsof n integers, are there elements a, b, c innumssuch that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]Solution 1:
Time complexity O(N³)，O(N*N-1*N-2)
Solution 2:
Time complexity O(N²)，Two pointer method. After we sort the nums List, nums would be like [-4, -1, -1 , 0, 1, 2]. In the beginning, nums[index] = -4, nums[secondIndex] = -1, and nums[thirdIndex] = 2. We would need complement 4(a+b+c = 0), but the sum of this pair is 3. Since the largest value we can use is 2, so we would let secondIndex plus 1. In orger to generate larger pair sum and vice versa.
How do we avoid the duplicate answer? By skipping nums[index] == nums[index-1]. And when the pair value equals the complement, we would adjust both the secondIndex and thirdIndex, until they both get different value than the pair we get. Hence, we can get the next pair whose pair value equals the complement.