两数之和问题是LeetCode上的一道经典算法题，也是面试中常见的问题。题目要求在一个整数数组中找到两个数，使它们的和等于一个特定的目标值，并返回这两个数的下标。
以下是多种解法：
- 暴力法： 最简单的方法是使用两个嵌套循环遍历数组中的所有可能组合，找到满足目标和的两个数。这种方法的时间复杂度为O(n^2)。
def twoSum(nums, target): n = len(nums) for i in range(n): for j in range(i+1, n): if nums[i] + nums[j] == target: return [i, j] return None
- 排序 + 双指针法： 先对数组进行排序，然后使用双指针从数组的两端开始向中间靠拢，根据和与目标值的大小关系来调整指针的位置。这种方法的时间复杂度为O(nlogn)，其中n是数组的长度。
def twoSum(nums, target): sorted_nums = sorted(nums) left, right = 0, len(nums)-1 while left < right: curr_sum = sorted_nums[left] + sorted_nums[right] if curr_sum == target: break elif curr_sum < target: left += 1 else: right -= 1 if left < right: # 在原数组中查找对应的下标 index1 = nums.index(sorted_nums[left]) index2 = nums.index(sorted_nums[right], index1+1) return [index1, index2] return None
- 使用集合（哈希表）： 这种方法类似于使用字典的解法，但是不需要存储每个数字对应的下标，只需要存储数字本身。遍历数组时，判断目标值与当前数字的差值是否在集合中，如果在，则找到了满足条件的两个数。
def twoSum(nums, target): num_set = set() for num in nums: complement = target - num if complement in num_set: index1 = nums.index(complement) index2 = nums.index(num, index1+1) return [index1, index2] num_set.add(num) return None
