数组1.Two Sum n²暴力解法哈希法

    技术2025-06-08  14

    题目要求

    从数组中找出两个数,这两个数加在一起等于目标值target,返回这两个数的下标

    暴力法

    思路

    指针 i 不动,指针 j 向后扫描数组,直到找到 nums[i] + nums[j] 的值等于 target 或者 j 大于数组长度为止 如果没找到,指针 i 加 1,重复上述过程,直到找到或者指针 i 大于数组长度为止

    代码

    class Solution(object): def twoSum(self, nums, target): length = len(nums) for i in range(0,length - 1): for j in range(i + 1,length): if nums[i] + nums[j] == target: return[i,j] return[]

    运行结果

    哈希法

    思路

    把数组中的数映射到散列表中,映射方法:数组的索引是散列表的值,数组的值是散列表的索引,即hashset [ nums [ i ] ] = i 一边映射一边查找散列表中索引为 target - nums[ i ] 的项是否为空,不为空就找到了结果 如果先映射后遍历会导致使用重复数值

    代码

    class Solution(object): def twoSum(self, nums, target): hashset = {} for i in range(len(nums)): if hashset.get(target - nums[i]) is not None: return[i,hashset.get(target-nums[i])] hashset[nums[i]] = i return []

    运行结果

    Processed: 0.012, SQL: 9