题目
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]]
such that i != j
, i != k
, and j != k
, and nums[i] + nums[j] + nums[k] == 0
.
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]]
Example 2:
Input: nums = []
Output: []
Example 3:
Input: nums = [0]
Output: []
Constraints:
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
思路
快慢指针,使用一个指针遍历数组,另外使用快慢指针置于数组的首尾。当三指针之和大于0时,快指针减一;三指针之和小于0时,慢指针进一;等于0时,则保存此时元素。
代码
python版本:
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i+1, len(nums)-1
while l < r:
if nums[l]+nums[r]+nums[i] > 0:
r -= 1
elif nums[l]+nums[r] + nums[i] < 0:
l += 1
else:
res.append(sorted([nums[l], nums[r], nums[i]]))
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1
r -= 1
return res