DeepSeek LeetCode 15.三数之和 Python3实现

pythonfrom typing import Listclass Solution:def threeSum(self, nums: List[int]) - List[List[int]]:nums.sort()n len(nums)res []for i in range(n - 2):# 排序后如果当前数大于 0后面不可能凑出和为 0if nums[i] 0:break# 跳过重复的 nums[i]避免重复三元组if i 0 and nums[i] nums[i - 1]:continueleft, right i 1, n - 1while left right:total nums[i] nums[left] nums[right]if total 0:left 1elif total 0:right - 1else:res.append([nums[i], nums[left], nums[right]])# 跳过重复的 nums[left]while left right and nums[left] nums[left 1]:left 1# 跳过重复的 nums[right]while left right and nums[right] nums[right - 1]:right - 1left 1right - 1return res思路排序 双指针1. 先对数组排序。2. 固定一个数 nums[i]然后用双指针 left 和 right 在剩余区间中寻找两个数使三数之和为 0。3. 根据当前三数之和与 0 的大小关系移动指针· 和小于 0left 右移· 和大于 0right 左移· 和等于 0记录结果并跳过重复的 left 和 right4. 固定数 nums[i] 也要跳过重复值避免重复三元组。时间复杂度 O(n²)空间复杂度 O(1)不考虑返回结果和排序栈空间