有序数组三数之和等于目标值的算法问题排查与最优解法咨询

现有代码的问题 #

• 初始指针位置不合理：你将k初始化为数组中间位置，直接跳过了靠近i的潜在解（比如测试用例中正确的k应该从i+1开始），导致搜索路径从一开始就偏离了正确方向。
• 指针移动逻辑错误：你的条件判断过于复杂且存在逻辑漏洞。以测试用例为例，第一次计算和为0+3+13=16>8后，错误地同时左移n和k，后续操作又让k降到0，触发i < k不成立的循环终止条件，完全没机会检查i=0,k=1,n=2的正确组合。
• 循环条件覆盖不足：i < k < n的写法虽然合法，但指针移动的逻辑可能导致k快速小于等于i，提前终止循环，遗漏有效解。

最优时间复杂度的解法（O(n²)） #

对于有序数组的三数之和问题，O(n²)是最优时间复杂度——因为问题本质需要遍历至少O(n²)种三元组组合，无法做到更低（比如O(n log n)）。

核心思路 #

固定一个指针作为第一个数的索引，然后用双指针分别指向剩余区间的首尾，通过调整双指针的位置来逼近目标和：

1. 遍历数组中的每个元素作为第一个数（索引i），范围为0到len(arr)-3（保证后续有k和n满足i<k<n）。
2. 对每个i，设置左指针k = i+1，右指针n = len(arr)-1。
3. 根据当前三数之和调整指针：
   • 和等于目标值t：直接返回对应索引（题目保证至少一个解，找到即可返回）。
   • 和大于t：右指针左移，减小总和。
   • 和小于t：左指针右移，增大总和。

实现代码 #

def threeSumSort(lst, t):
    res = []
    length = len(lst)
    for i in range(length - 2):
        k = i + 1
        n = length - 1
        while k < n:
            current_sum = lst[i] + lst[k] + lst[n]
            if current_sum == t:
                res.append([i+1, k+1, n+1])
                return res  # 题目保证存在解，找到后直接返回
            elif current_sum > t:
                n -= 1
            else:
                k += 1
    return res

lst = [0,2,3,5,10,13]
print(threeSumSort(lst, 8))  # 输出 [1,2,3]

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