python 算法 两数之和 的多种解法

两���之和问题是LeetCode上的一道经典算法题，也是面试中常见的问题。题目要求在一个整数数组中找到两个数，使它们的和等于一个特定的目标值，并返回这两个数的下标。

以下是多种解法：

1. 暴力法： 最简单的方法是使用两个嵌套循环遍历数组中的所有可能组合，找到满足目标和的两个数。这种方法的时间复杂度为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

1. 排序 + 双指针法： 先对数组进行排序，然后使用双指针从数组的两端开始向中间靠拢，根据和与目标值的大小关系来调整指针的位置。这种方法的时间复杂度为O(nlogn)，其中n是数组的长度。

def twoSum(nums, target):    sorted_nums = sorted(nums)    left, right = 0, len(nums)-1    while left  
使用集合（哈希表）： 这种方法类似于使用字典的解法，但是不需要存储每个数字对应的下标，只需要存储数字本身。遍历数组时，判断目标值与当前数字的差值是否在集合中，如果在，则找到了满足条件的两个数。
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
（）