力扣热题三数之和python

### LeetCode 三数之和问题的 Python 解法 对于给定的一个包含 n 个整数的数组 nums，判断是否存在三个元素 a, b, c ，使得 a + b + c = 0？找出所有满足条件且不重复的三元组。 #### 方法一：暴力求解 (超时) 最直观的方法是对每个可能的组合进行遍历并检查其总和是否等于零。然而这种方法的时间复杂度为 O(n³)，当数据量较大时会超出时间限制[^2]。 ```python def threeSum(nums): result = [] length = len(nums) for i in range(length-2): for j in range(i+1,length-1): for k in range(j+1,length): if nums[i]+nums[j]+nums[k]==0: temp=[nums[i],nums[j],nums[k]] temp.sort() if temp not in result: result.append(temp) return result ``` 此方法虽然可以解决问题但是效率低下，在实际应用中并不推荐使用。 #### 方法二：哈希表优化 为了提高性能，可以在两层循环的基础上利用哈希集合来存储已经访问过的数值及其索引位置，从而快速定位第三个数的位置。这样做的好处是可以减少一层显式的嵌套循环，降低算法的整体开销至O(n²)[^5]。 ```python from collections import defaultdict class Solution(object): def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ res = set() seen = {} for index_i,i in enumerate(nums[:-2]): if i not in seen: seen[i]=index_i for j in nums[index_i+1:]: target=-i-j if target in seen and seen[target]!=index_i : triplet=tuple(sorted([i,j,target])) if triplet not in res: res.add(triplet) return list(map(list,res)) ``` 上述实现通过 `set` 来去重，并且借助字典记录已处理过的目标值，有效防止了重复项的加入。 #### 方法三：双指针技巧 先对输入列表进行排序操作，之后固定第一个数字作为当前考虑的一部分；接着采用两个游标的策略——左端指向下一个待考察元素而右端则位于序列末端。根据这三个选定元素计算得到的结果调整两端游标直至找到符合条件或者无法继续为止。该方案同样具有较好的时空表现特性，适用于大多数情况下的需求[^1]。 ```python class Solution(object): def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ nums.sort() N=len(nums) ans=[] for t in range(N-2): if t>0 and nums[t]==nums[t-1]: continue l,r=t+1,N-1 while l<r: total=nums[t]+nums[l]+nums[r] if total==0: ans.append((nums[t],nums[l],nums[r])) while l<N-1 and nums[l]==nums[l+1]:l+=1 while r>0 and nums[r]==nums[r-1]:r-=1 l+=1;r-=1 elif total<0:l+=1 else:r-=1 return ans ``` 这段代码实现了基于双指针技术的有效解决方案，能够高效地解决三数之和的问题。