LeetCode两数之和：除字典解法外还有其他实现方式吗？

你已经用哈希表（字典）实现了最优的O(n)时间复杂度解法，除此之外还有两种常见的实现方式：

1. 暴力枚举法 #

这是最直观的思路，直接遍历数组中所有两两组合的元素，检查它们的和是否等于target。因为题目保证有唯一解，找到符合条件的下标对就可以直接返回。

代码实现：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]

这种方法的时间复杂度是O(n²)，空间复杂度O(1)，适合小体量的数组，但数据量大时效率会很低。

2. 排序+双指针法 #

先将数组元素与原索引绑定，然后按元素值排序，再用左右两个指针从数组两端向中间移动：

• 如果左右指针指向的元素和小于target，左指针右移（增大当前和）
• 如果和大于target，右指针左移（减小当前和）
• 等于target时，返回两个元素的原索引

代码实现：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 绑定元素与原索引
        sorted_nums = sorted([(val, idx) for idx, val in enumerate(nums)], key=lambda x: x[0])
        left = 0
        right = len(sorted_nums) - 1
        while left < right:
            current_sum = sorted_nums[left][0] + sorted_nums[right][0]
            if current_sum == target:
                return [sorted_nums[left][1], sorted_nums[right][1]]
            elif current_sum < target:
                left += 1
            else:
                right -= 1

这种方法的时间复杂度主要由排序决定，是O(n log n)，空间复杂度O(n)（需要存储带索引的排序数组），效率介于暴力法和哈希表法之间。

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