三数之和【双指针】

Problem: 15. 三数之和

思路 & 解题方法

两数相加的加强版，先确定第一个数，然后从右边去用双指针找另外两个数。注意题目需要避免重复的答案，所以要注意处理这个问题。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n^2)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort()length = len(nums)ans = []for i in range(length):if i > 0 and nums[i] == nums[i - 1]:continuetarget, left, right = -nums[i], i + 1, length - 1while left < right:now = nums[left] + nums[right]if now > target:right -= 1elif now < target:left += 1else:ans.append([nums[i], nums[left], nums[right]])while left < right and nums[left] == nums[left + 1]:left += 1while left < right and nums[right] == nums[right - 1]:right -= 1left += 1right -= 1return ans