Leetcode三数之和问题优化：二分查找/哈希表实现遇异常求助

问题背景 #

正在解决三数之和问题：找出数组中所有和为0的不重复三元组。原始双重循环代码运行超时，尝试用二分查找优化后性能仍不达标，怀疑二分实现有误；改用哈希表实现后结果集为空，需要定位问题并给出优化方案。

原始代码分析 #

def zeroSumTriplets(nums):
    result = set()
    for i,a in enumerate(nums[:-2],1):
        for j,b in enumerate(nums[i:-1],i+1):
            if -a-b not in nums[j:]: continue
            triplet = tuple(sorted([a,b,-a-b]))
            result.add(triplet)
    return list(result)

• 核心性能问题：每次判断-a-b not in nums[j:]是线性查找（时间复杂度O(n)），叠加两层嵌套循环后整体复杂度为O(n³)，数据量稍大就会超时。
• 逻辑错误：enumerate(nums[:-2],1)的起始索引设为1，会漏掉数组第一个元素作为三元组第一个值的情况，导致结果不完整。

二分查找优化的错误点 #

class Solution(object):
    def threeSum(self, nums):
        nums.sort()
        result = set()
        for i,a in enumerate(nums[:-2],1):
            for j,b in enumerate(nums[i:-1],i+1):
                mid = j + int(round((len(nums)-j)/2))
                if a + b + nums[mid] >= 0:
                    if -a-b not in nums[j:mid]:continue
                    triplet = tuple(sorted([a,b,-a-b]))
                    result.add(triplet)

                else:
                    if -a-b not in nums[mid:]:continue
                    triplet = tuple(sorted([a,b,-a-b]))
                    result.add(triplet)          
        return list(result)

1. 二分逻辑完全失效：仅通过中间位置划分区间，后续的in操作依然是线性查找，根本没利用到二分查找O(logn)的效率优势，等于没做优化。
2. 起始索引错误：同样用enumerate(...,1)跳过了数组第一个元素，遗漏部分合法三元组。
3. 冗余操作：数组已提前排序，三元组可直接按顺序构造，无需再次排序，浪费时间。

哈希表实现的问题根源 #

class Solution(object):
    def threeSum(self, nums):
        hashtable = dict()
        result = set()
        for i in range(len(nums)):
            hashtable[i] = nums[i]
        for i in range(len(nums)):
            a = nums[i]
            for j in range(i + 1, len(nums)):
                b = nums[j]
                try:
                    if hashtable[-(a+b)] > j:
                        triplet = tuple(sorted([a,b,-a-b]))
                        result.add(triplet)
                except:
                    continue
        return list(result)

• 哈希表构建逻辑颠倒：你把索引作为键、元素值作为值存入哈希表，但后续查找时用hashtable[-(a+b)]，是用目标元素值当键去查询，而哈希表的键是索引，自然查不到任何结果，导致返回空集。
• 正确的哈希表构建应该是：键为元素值，值为该元素对应的所有索引列表，这样才能通过目标值-(a+b)找到对应的索引，进而判断是否存在符合条件的第三个元素。

正确的优化方案 #

方案1：双指针法（最优解，时间复杂度O(n²)） #

先排序数组，固定第一个元素后用左右指针在剩余区间寻找和为-nums[i]的两个元素，同时跳过重复元素避免结果冗余。

class Solution(object):
    def threeSum(self, nums):
        nums.sort()
        result = []
        n = len(nums)
        for i in range(n - 2):
            # 跳过重复的第一个元素
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left = i + 1
            right = n - 1
            target = -nums[i]
            while left < right:
                current_sum = nums[left] + nums[right]
                if current_sum == target:
                    result.append([nums[i], nums[left], nums[right]])
                    # 跳过左指针重复值
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    # 跳过右指针重复值
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif current_sum < target:
                    left += 1
                else:
                    right -= 1
        return result

方案2：修复后的哈希表实现 #

class Solution(object):
    def threeSum(self, nums):
        result = set()
        n = len(nums)
        # 构建元素到索引列表的哈希表
        num_indices = {}
        for idx, num in enumerate(nums):
            if num not in num_indices:
                num_indices[num] = []
            num_indices[num].append(idx)
        
        for i in range(n):
            a = nums[i]
            for j in range(i + 1, n):
                b = nums[j]
                target = -(a + b)
                if target not in num_indices:
                    continue
                # 遍历所有target对应的索引，找到大于j的
                for k in num_indices[target]:
                    if k > j:
                        # 利用排序去重
                        triplet = tuple(sorted([a, b, target]))
                        result.add(triplet)
                        # 找到一个就够，避免重复添加
                        break
        return list(result)

内容的提问来源于stack exchange，提问作者levlevon