在Python算法的世界里，有一座神秘的宝藏，等着我们去发掘。这座宝藏就是经典题目——“两数之和”。今天，作为宝藏猎人的我们将展开一场冒险，找到不同的解题思路和技巧，揭开这道谜题的神秘面纱。

任务说明

你是一位宝藏猎人，拥有一个神秘的数字宝箱 nums，里面装着一系列隐藏的整数。你的任务是找到两个神秘数字，这两个数字的和恰好等于一个传说中的神秘数字 target，也就是你的目标值。

但任务有些限制：

每个数字只能使用一次，别想着重复使用相同的数字。

宝藏中的每个谜题（输入）只有一个解答（答案是唯一的）。

你的挑战是找到这两个数字，并迅速返回它们在宝箱中的位置（数组下标），以揭开目标值的谜底！

示例 1：

宝藏 nums = [2, 7, 11, 15]，目标值 target = 9

答案是 [0, 1]，因为宝藏中的数字 nums[0] 和 nums[1] 相加正好等于目标值 9！

你能通过这道谜题，找到那两个神秘的数字吗？

看起来很简单？两个数加起来等于 target，找出它们在数组中的位置。不就是加法嘛！但要快，甚至比计算机更快。这可是考验智慧和技巧的绝佳机会。

解法一：暴力解法

首先，我们作为一名初出茅庐的猎人，可能会想到最直接的方法，那就是——暴力破解。

思路：

遍历数组中的每个数字，尝试与后面的每个数字相加，看看是否等于目标值。只要找到符合条件的两个数，就返回它们的下标。

代码实现：

def two_sum(nums, target):

    for i in range(len(nums)):

        for j in range(i + 1, len(nums)):

            if nums[i] + nums[j] == target:

                return [i, j]

时间复杂度分析：

时间复杂度：O(n²)，因为我们需要遍历两次数组。

空间复杂度：O(1)，不需要额外的存储空间。

优点：

简单易懂，逻辑清晰。

缺点：

当数组变大时，效率急剧下降，计算量成倍增加。

解法二：哈希表解法

作为一位资深猎人，我们当然不想一直使用暴力。现在，我们祭出哈希表（字典）的法宝。这可是算法世界中的利器！通过它，我们能够一遍遍历数组，轻松解决问题。

思路：

使用哈希表记录每个数字的值及其下标。在遍历数组时，对于每个元素 num，我们可以计算出目标值 target 和当前值的差 complement = target - num。如果 complement 已经存在于哈希表中，那我们就找到了答案。

代码实现：

def two_sum(nums, target):

    hashmap = {}

    for i, num in enumerate(nums):

        complement = target - num

        if complement in hashmap:

            return [hashmap[complement], i]

        hashmap[num] = i

时间复杂度分析：

时间复杂度：O(n)，因为我们只需遍历数组一次。

空间复杂度：O(n)，需要额外的存储空间来保存哈希表中的元素。

优点：

高效！单次遍历即可解决问题，非常适合处理大数据量的情况。

不再需要嵌套循环，极大提升了算法性能。

缺点：

需要额外的空间来存储哈希表。

解法三：双指针法（适用于有序数组）

猎人的工具箱中永远不止哈希表一件神器。面对有序的数组，我们可以使用更为巧妙的双指针法，进一步简化操作。这种方法就像同时派出两位猎人，从数组的两端开始寻找目标。

思路：

首先，我们需要将数组排序，然后设置两个指针，分别指向数组的开头和末尾。如果两者之和等于目标值，就返回。如果和小于目标值，左指针右移；如果和大于目标值，右指针左移。

代码实现：

def two_sum_sorted(nums, target):

    nums_sorted = sorted(enumerate(nums), key=lambda x: x[1])  # 排序并记录原始下标

    left, right = 0, len(nums) - 1

    while left < right:

        sum_ = nums_sorted[left][1] + nums_sorted[right][1]

        if sum_ == target:

            return [nums_sorted[left][0], nums_sorted[right][0]]

        elif sum_ < target:

            left += 1

        else:

            right -= 1

时间复杂度分析：

时间复杂度：O(n \log n)，主要因为排序需要 O(n \log n) 的时间。

空间复杂度：O(n)，需要额外空间来存储排序后的数组。

优点：

在数组有序的情况下，非常高效，逻辑也十分简单。

缺点：

如果数组无序，必须先排序，导致时间复杂度变高。

解法四：减少空间的哈希表

最后，作为精打细算的猎人，我们希望进一步优化，减少哈希表占用的空间。有时候，我们并不需要保存全部元素的信息，只需关注已经遍历的部分即可。

思路：

在遍历过程中，先判断当前元素的 "目标值差" 是否在哈希表中，如果不在，再将当前元素存入哈希表。这样就避免了遍历数组时多余的存储操作。

代码实现：

def two_sum(nums, target):

    hashmap = {}

    for i, num in enumerate(nums):

        complement = target - num

        if complement in hashmap:

            return [hashmap[complement], i]

        hashmap[num] = i

时间复杂度分析：

时间复杂度：O(n)，只需遍历一次数组。

空间复杂度：O(n)，与之前的哈希表解法类似。

优点：

保持哈希表的高效性，并且逻辑上更加简洁。

总结

在这次的猎人任务中，我们学到了多种解题思路：

暴力破解：简单直接，但效率较低。

哈希表解法：一次遍历搞定，非常高效。

双指针法：适用于有序数组，通过左右指针移动快速找到答案。

减少空间的哈希表：优化存储效率，在不影响速度的情况下减少空间占用。

每种方法都有自己的优点和适用场景，作为一名优秀的算法猎人，选择合适的工具和策略至关重要。在实际的项目和算法竞赛中，灵活使用这些技巧，将帮助你快速解决问题。