python 算法 两数之和 的多种解法_两数之和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 < 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

1. 使用集合（哈希表）： 这种方法类似于使用字典的解法，但是不需要存储每个数字对应的下标，只需要存储数字本身。遍历数组时，判断目标值与当前数字的差值是否在集合中，如果在，则找到了满足条件的两个数。

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