👤作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
暴力破解
其基本思想是遍历数组的每个元素 x，并查找是否存在一个值与 x 相加之和等于目标值 target。这种方法需要两层循环：外层循环遍历每个元素，内层循环查找是否存在符合条件的另一个元素
from typing import List def twoSum(nums: List[int], target: int) -> List[int]: """ Find two numbers such that they add up to a specific target number. Args: nums (List[int]): List of integers. target (int): The target sum. Returns: List[int]: Indices of the two numbers adding up to target, if any. """ # 外层循环 for i in range(len(nums)): # 内层循环，查找配对 for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return [i, j] return [] def main(): """ Main function to test the twoSum function. """ nums = [2, 7, 11, 15] target = 9 result = twoSum(nums, target) print(f"Indices of the two numbers: {result}") if __name__ == '__main__': main()
哈希表
一种直观的方法是使用两层循环，对每对可能的数字进行求和并比较是否等于目标值。但这种方法的时间复杂度较高，为O(n^2)。
一个更高效的方法是使用哈希表来减少查找时间。这种方法的基本思想是，遍历数组，对于每个元素，我们可以计算出其配对的数字（即 target - 当前数字），然后在哈希表中查找是否存在这样一个配对数字。如果存在，则直接返回当前数字和配对数字的下标。在遍历的过程中，将每个元素的值和它的索引添加到哈希表中，这样在查找配对数字时就可以快速进行。代码在练习的时候建议都加上注释方便阅读也更规范。
def twoSum(nums, target): """ Finds two numbers such that they add up to a specific target number. :param nums: List of integers. :param target: Integer, the target sum. :return: A list containing the indices of the two numbers that add up to the target. """ hashmap = {} for i, num in enumerate(nums): complement = target - num if complement in hashmap: return [hashmap[complement], i] hashmap[num] = i return [] def main(): """ Main function to demonstrate the usage of twoSum function. """ nums = [2,7,11,15] target = 9 result = twoSum(nums, target) print(f"Indices of the two numbers that add up to {target}: {result}") if __name__ == '__main__': main()
输出
解释
- 初始化一个空字典（哈希表）
hashmap。 - 遍历数组
nums，其中i是当前数字的索引，num是当前数字的值。 - 计算
complement，即目标值target减去当前数字num。 - 如果
complement在hashmap中，意味着我们找到了一个解，返回[hashmap[complement], i]，这里hashmap[complement]是配对数字的索引，i是当前数字的索引。 - 如果当前遍历的数字不是解的一部分，将其添加到
hashmap中，键为数字的值，值为它的索引。 - 如果遍历完整个数组都没有找到解，返回一个空列表。
这种方法的时间复杂度为O(n)，因为我们只需要遍历一次数组，查找时间为O(1)。
劣势
空间开销：哈希表的主要劣势之一是它需要额外的空间来存储数据结构。对于大型数据集，这可能会成为问题，尤其是在内存资源受限的情况下。
