01_两数之和

一、题目

'''
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。变种：这个题目可以让返回多组数字、有序返回、多数之和
'''

二、思路：

1、首先，确定比较的维度：比较的目标值是整数，那么，要把数组里的元素，按整数的形式，去和target去比较
2、其次，找到题目中包含的关系：随便选一个元素X，与target，另一个元素y应该是应该等于target-x，且x!=y
3、然后，明确要返回的类型：数组下标。所以本题的主角是用下标表示整数去比较。元素转化为下标，不太方便，但是下标转化为元素，比较容易。list[下标]=元素
4、最后，选择算法思路：

三、解法

暴力枚举：循环法

写法1：结果报错：list[i] + list[j] == target
class Solution:def twoSum(self,nums:list[int],target:int):n = len(nums)for i in range(n-1):for j in range(i+1,n-1):if list[i] + list[j] == target:return [i,j]return []程序报错的原因是在内部循环中，你使用了list[i]和list[j]来访问列表元素，但是应该使用nums[i]和nums[j]

写法2：结果[0,1]---简单版本，只返回第一对符合target的元素索引
class Solution:def twoSum(self,nums:list[int],target:int):n = len(nums)for i in range(n-1):for j in range(i+1,n-1):if nums[i] + nums[j] == target:return [i,j]return []if __name__ == '__main__':nums = [2,7,4,5,11,15]solution = Solution()result = solution.twoSum(nums,9)print(result)

写法3：结果[[0, 1], [2, 3]]
class Solution:def twoSum(self, nums: list[int], target: int):n = len(nums)result = []for i in range(n-1):for j in range(i+1, n):if nums[i] + nums[j] == target:result.append([i, j])return resultif __name__ == '__main__':nums = [2, 7, 4, 5, 11, 15]solution = Solution()result = solution.twoSum(nums, 9)print(result)

哈希表法：字典法

# 写法一：问题不会写
class Solution:def twoSum(self,nums:list[int],target:int):hash_map ={}n = len(nums)for i,nums in enumerate(nums):x  = target - nums[i] #明明已经知道了num表示元素值，非要用nums[i]来表示。nums[i] == xif x in #结果到这一步不知道该咋写了# 如何表示x的索引？#如果不在，怎么表示把num和i放到哈希表？

# 写法二：输出结果是[],因为缺少将遍历到的每个 num 及其索引 i 存入 hash_map的操作，结果只能返回[]
class Solution:def twoSum(self, nums: list, target: int) :hash_map = {}for i, num in enumerate(nums):x = target - numif x in hash_map:return [hash_map[x], i]#上面返回的空返回是是这个哦return []#不是这个

#写法三： 输出是 [0, 1] ，只返回一对解，默认是第一对
class Solution:def twoSum(self, nums: list, target: int) :hash_map = {}for i, num in enumerate(nums):x = target - numif x in hash_map:return [hash_map[x], i]hash_map[num] = i #表示把遍历到的元素存储到哈希表中return []if __name__ == '__main__':nums = [2, 7, 4, 5, 11, 15]target = 9solution = Solution()result = solution.twoSum(nums, target)print(result)  # 输出应该是 [0, 1]，因为 nums[0] + nums[1] == 9

#写法4：需要返回多个解的时候
class Solution:def twoSum(self, nums: list, target: int):hash_map = {}result = []for i, num in enumerate(nums):complement = target - numif complement in hash_map:result.append([hash_map[complement], i])hash_map[num] = ireturn resultif __name__ == '__main__':nums = [2, 7, 4, 5, 11, 15]target = 9solution = Solution()results = solution.twoSum(nums, target)for result in results:print(result)  # 打印所有满足条件的索引对

四、学习总结

1、返回值的格式
在Python中，返回值 return [i, j] 和 return (i, j) 在大多数情况下效果相同，因为它们都会返回一个包含两个元素的序列。不过，它们返回的类型不同：
return [i, j] 返回的是一个列表（list），这是一个可变的序列类型。
return (i, j) 返回的是一个元组（tuple），这是一个不可变的序列类型。
在“两数之和”的问题中，我们通常返回一个包含两个索引的序列，以便调用者可以知道这两个数在原数组中的位置。使用列表或元组都可以达到这个目的，但元组更常用2、需要返回多组元素的时候，不满足条件的返回值：
如果找不到满足条件的元素对，实际上程序将返回一个空列表[]，因为result初始化为空列表，并且只有当找到满足条件的元素对时才会向result中添加元素。
如果没有找到任何满足条件的元素对，循环结束后result仍然是空的，所以直接返回result就可以了。3、索引，就是角标、下标4、range(5) 生成的是从0开始到5结束的整数序列，但不包括5。它包含的数字是：0, 1, 2, 3, 4。所以不需要 range(n-1)5、enumerate函数：
在Python中，enumerate 是一个内置函数，它用于将一个可遍历的数据对象（如列表、元组或字符串）组合为一个索引序列，同时列出数据和数据下标。
这通常用于for循环中，使你能够在遍历过程中同时获取每个元素及其对应的索引。6、哈希表：
在Python中，哈希表通常通过字典（dict）这种数据结构来实现。字典是一个无序的键值对集合
hash_map = {2: 0,7: 1,11: 2,15: 3
}hash_map[key]=value,也就是hash_map[2]=0，hash_map[11]=27、为什么在哈希表中，key是数组中的元素值，而value是索引值呢，为什么不是key是索引值，而value是元素值呢
其实是可以，但是结果都一样，因为hash_map[key]=value，如果索引是key,元素值就是value,总是能一一映射的8、因为上面的结果都是 return [i,j],这样只会返回一个数据，需要返回多个数据，需要定义一个result =[],然后在返回值里面
单个： return [i,j]
多个： result.append([i，j]),return resultreturn result 会包含结果为空的情况。如果数组中没有任何一对数字的和等于目标值 target，那么 result 列表将保持为空（result 初始为空[]），函数最终会返回一个空列表 []。

五、全

#两数之和
'''
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。变种：这个题目可以让返回多组数字、有序返回、多数之和
'''# 解：
# 1、首先，确定比较的维度：比较的目标值是整数，那么，要把数组里的元素，按整数的形式，去和target去比较
# 2、其次，找到题目中包含的关系：随便选一个元素X，与target，另一个元素y应该是应该等于target-x，且x!=y
# 3、然后，明确要返回的类型：数组下标。所以本题的主角是用下标表示整数去比较。元素转化为下标，不太方便，但是下标转化为元素，比较容易。list[下标]=元素
# 4、最后，选择算法思路：# tips:只给一个数组，用下标表示元素'''
一、暴力枚举法
暴力枚举--for循环，随便选择x，看y是否在数组里面。写法1：结果报错：list[i] + list[j] == target
class Solution:def twoSum(self,nums:list[int],target:int):n = len(nums)for i in range(n-1):for j in range(i+1,n-1):if list[i] + list[j] == target:return [i,j]return []程序报错的原因是在内部循环中，你使用了list[i]和list[j]来访问列表元素，但是应该使用nums[i]和nums[j]写法2：结果[0,1]---简单版本，只返回第一对符合target的元素索引
class Solution:def twoSum(self,nums:list[int],target:int):n = len(nums)for i in range(n-1):for j in range(i+1,n-1):if nums[i] + nums[j] == target:return [i,j]return []if __name__ == '__main__':nums = [2,7,4,5,11,15]solution = Solution()result = solution.twoSum(nums,9)print(result)写法3：结果[[0, 1], [2, 3]]
class Solution:def twoSum(self, nums: list[int], target: int):n = len(nums)result = []for i in range(n-1):for j in range(i+1, n):if nums[i] + nums[j] == target:result.append([i, j])return resultif __name__ == '__main__':nums = [2, 7, 4, 5, 11, 15]solution = Solution()result = solution.twoSum(nums, 9)print(result)
''''''
上面学习到的点：1、返回值的格式
在Python中，返回值 return [i, j] 和 return (i, j) 在大多数情况下效果相同，因为它们都会返回一个包含两个元素的序列。不过，它们返回的类型不同：
return [i, j] 返回的是一个列表（list），这是一个可变的序列类型。
return (i, j) 返回的是一个元组（tuple），这是一个不可变的序列类型。
在“两数之和”的问题中，我们通常返回一个包含两个索引的序列，以便调用者可以知道这两个数在原数组中的位置。使用列表或元组都可以达到这个目的，但元组更常用2、需要返回多组元素的时候，不满足条件的返回值：
如果找不到满足条件的元素对，实际上程序将返回一个空列表[]，因为result初始化为空列表，并且只有当找到满足条件的元素对时才会向result中添加元素。
如果没有找到任何满足条件的元素对，循环结束后result仍然是空的，所以直接返回result就可以了。3、索引，就是角标、下标
4、range(6) 生成的是从0开始到5结束的整数序列，但不包括6。具体来说，它包含的数字是：0, 1, 2, 3, 4, 5。所以不需要 range(n-1)
''''''
二、哈希表法：字典法# 写法一：问题不会写
class Solution:def twoSum(self,nums:list[int],target:int):hash_map ={}n = len(nums)for i,nums in enumerate(nums):x  = target - nums[i] #明明已经知道了num表示元素值，非要用nums[i]来表示。nums[i] == xif x in #结果到这一步不知道该咋写了# 如何表示x的索引？#如果不在，怎么表示把num和i放到哈希表？# 写法二：输出结果是[],因为缺少将遍历到的每个 num 及其索引 i 存入 hash_map的操作，结果只能返回[]
class Solution:def twoSum(self, nums: list, target: int) :hash_map = {}for i, num in enumerate(nums):x = target - numif x in hash_map:return [hash_map[x], i]#上面返回的空返回是是这个哦return []#不是这个#写法三： 输出是 [0, 1] ，只返回一对解，默认是第一对
class Solution:def twoSum(self, nums: list, target: int) :hash_map = {}for i, num in enumerate(nums):x = target - numif x in hash_map:return [hash_map[x], i]hash_map[num] = i #表示把遍历到的元素存储到哈希表中return []if __name__ == '__main__':nums = [2, 7, 4, 5, 11, 15]target = 9solution = Solution()result = solution.twoSum(nums, target)print(result)  # 输出应该是 [0, 1]，因为 nums[0] + nums[1] == 9#写法4：需要返回多个解的时候
class Solution:def twoSum(self, nums: list, target: int):hash_map = {}result = []for i, num in enumerate(nums):complement = target - numif complement in hash_map:result.append([hash_map[complement], i])hash_map[num] = ireturn resultif __name__ == '__main__':nums = [2, 7, 4, 5, 11, 15]target = 9solution = Solution()results = solution.twoSum(nums, target)for result in results:print(result)  # 打印所有满足条件的索引对''''''
学习到的：
1、enumerate函数：
在Python中，enumerate 是一个内置函数，它用于将一个可遍历的数据对象（如列表、元组或字符串）组合为一个索引序列，同时列出数据和数据下标。
这通常用于for循环中，使你能够在遍历过程中同时获取每个元素及其对应的索引。2、哈希表：
在Python中，哈希表通常通过字典（dict）这种数据结构来实现。字典是一个无序的键值对集合
hash_map = {2: 0,7: 1,11: 2,15: 3
}hash_map[key]=value,也就是hash_map[2]=0，hash_map[11]=23、为什么在哈希表中，key是数组中的元素值，而value是索引值呢，为什么不是key是索引值，而value是元素值呢
其实是可以，但是结果都一样，因为hash_map[key]=value，如果索引是key,元素值就是value,总是能一一映射的4、因为上面的结果都是 return [i,j],这样只会返回一个数据，需要返回多个数据，需要定义一个result =[],然后在返回值里面
单个： return [i,j]
多个： result.append([i，j]),return resultreturn result 会包含结果为空的情况。如果数组中没有任何一对数字的和等于目标值 target，那么 result 列表将保持为空（result 初始为空[]），函数最终会返回一个空列表 []。'''