【LeetCode】1. 两数之和

描述

  给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。

  只存在一个有效答案，不能使用两次相同的元素，可按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

Python

一、双指针枚举

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
    	# 计算数组长度
        n = len(nums)

		# 双指针枚举
        for i in range(n):
            for j in range(i + 1, n):
            	# 匹配
                if nums[i] + nums[j] == target:
                    return [i, j]

二、哈希查找

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 计算数组长度，初始化哈希表
        length, numMap = len(nums), {}

        # 建立哈希映射：nums[index] -> index
        for i in range(length):
            numMap[nums[i]] = i

        # 在哈希表中查询 nums[index] 对应的加数
        for i in range(length):
            # 计算对应加数
            num = target - nums[i]
            # 匹配，索引排重
            if (num in numMap) and (i != numMap[num]):
                # 返回数组下标
                return [i, numMap[num]]