背景給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，n判斷 nums 中是否存在三個(gè)元素 a，b，c n，使得 a + b + c = 0 ？請(qǐng)你找出n所有滿足條件且不重復(fù)

背景

給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，n判斷 nums 中是否存在三個(gè)元素 a，b，c n，使得 a + b + c = 0 ？請(qǐng)你找出n所有滿足條件且不重復(fù)的三元組n

解題思路

#排序 + 雙指針n本題的難點(diǎn)在于如何去除重復(fù)解nn# 算法流程：nn特判，對(duì)于數(shù)組長(zhǎng)度 nn，如果數(shù)組為 nullnull 或者數(shù)組長(zhǎng)度小于 33，返回 []。nn對(duì)數(shù)組進(jìn)行排序。nn遍歷排序后數(shù)組：n若 nums[i]>0：因?yàn)橐呀?jīng)排序好，所以后面不可能有三個(gè)數(shù)加和等于 00，直接返回結(jié)果。nn對(duì)于重復(fù)元素：跳過(guò)，避免出現(xiàn)重復(fù)解nn令左指針 L=i+1L=i+1，右指針 R=n-1R=n?1，當(dāng) L<RL<R 時(shí)，執(zhí)行循環(huán)：n當(dāng) nums[i]+nums[L]+nums[R]==0nums[i]+nums[L]+nums[R]==0，執(zhí)行循環(huán)，判斷左界和右界是否和下一位置重復(fù)，去除重復(fù)解。并同時(shí)將 L,RL,R 移到下一位置，尋找新的解n若和大于 0，說(shuō)明 nums[R]nums[R] 太大，RR 左移n若和小于 0，說(shuō)明 nums[L]nums[L] 太小，LL 右移nn# 復(fù)雜度分析n時(shí)間復(fù)雜度:O(n2)n空間復(fù)雜度：O(1)

解法

class Solution:n def threeSum(self, nums: List[int]) -> List[List[int]]:n if len(nums) < 3:n return []n n nums.sort()n res= []n n = len(nums)n for index,value in enumerate(nums):n if value > 0:n return resn if index > 0 and nums[index] == nums[index-1]:n continuen n left = index + 1n right = n - 1n while left < right:n if nums[index] + nums[left] + nums[right] == 0:n res.append([nums[index],nums[left],nums[right]])n while left < right and nums[left] == nums[left+1]:n left +=1n while left < right and nums[right] == nums[right-1]:n right -=1n left +=1n right -=1n elif nums[index] + nums[left] + nums[right] > 0:n right -=1n else:n left +=1n return res