Codewars两数之和Python代码部分测试用例不通过求助

核心问题分析 #

你的代码存在关键逻辑错误，导致无法通过测试用例：

• 直接调用nums.sort()修改了原数组的元素顺序，返回的[l, r]是排序后数组的索引，但题目要求返回原数组中对应元素的原始索引，这是测试失败的主要原因。
• 未保留原始索引的情况下，双指针法的结果完全不符合题目要求。

解决方案 #

方案1：哈希表法（最优时间复杂度） #

利用哈希表存储已遍历元素的原始索引，遍历过程中快速查找目标补数：

def two_sum(nums, target):
    num_index_map = {}
    for idx, num in enumerate(nums):
        complement = target - num
        if complement in num_index_map:
            return [num_index_map[complement], idx]
        num_index_map[num] = idx
    return []

• 时间复杂度：O(n)，仅需一次遍历
• 空间复杂度：O(n)，用于存储哈希表

方案2：保留原索引的双指针法 #

如果坚持使用双指针思路，需要先保存元素与原索引的关联，再进行排序操作：

def two_sum(nums, target):
    # 绑定元素与原始索引
    indexed_elements = [(num, idx) for idx, num in enumerate(nums)]
    # 按元素值排序
    indexed_elements.sort()
    
    left, right = 0, len(indexed_elements) - 1
    while left < right:
        current_sum = indexed_elements[left][0] + indexed_elements[right][0]
        if current_sum == target:
            # 返回原始索引
            return [indexed_elements[left][1], indexed_elements[right][1]]
        elif current_sum > target:
            right -= 1
        else:
            left += 1
    return []

• 时间复杂度：O(n log n)，主要来自排序操作
• 空间复杂度：O(n)，用于存储元素与索引的关联列表

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