LeetCode|LeetCode 1. 两数之和 LeetCode1.两数之和

文章图片

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

题解
【LeetCode|LeetCode 1. 两数之和】备注:没有进行输入检查,默认是有效输入数据.
暴力双重循环
最简单的,一下子想到的,双重循环遍历查找,第一层i:begin->end,第二次j:i+1->end

class Solution { public: vector twoSum(vector& nums, int target) { for(int i = 0; i < nums.size(); i++) { int tmp = target - nums[i]; for(int j = i + 1; j < nums.size(); j++) { if(tmp == nums[j]) return vector{i,j}; } } return vector{-1,-1}; } };

执行用时：460 ms, 在所有 C++ 提交中击败了39.91%的用户
内存消耗：8.9 MB, 在所有 C++ 提交中击败了36.09%的用户
思考一下,使用双重循环,时间复杂度应该是在O(n^2).
哈希字典
稍加思索,感觉这种有查找的,可以使用哈希字典来提升下速度.
思路如下: 1. 遍历一次数组,将其填充到哈希字典中,key为数组值,value为数组下标.如果有重复的元素,只会记录最后一次出现的索引. 2. 遍历一次数组,查找相应值,要注意遍历时候的数组索引和.

class Solution { public: vector twoSum(vector& nums, int target) {unordered_map m; for(int i = 0; i 0 && m[tmp] != i) { return vector{i,m[tmp]}; } } return vector{-1,-1}; } };

执行用时：16 ms, 在所有 C++ 提交中击败了75.88%的用户
内存消耗：9.9 MB, 在所有 C++ 提交中击败了10.90%的用户
从执行时间来看,应该还是有更好的解法.稍加思索,没想出来,看下题解.
哈希字典,插入时检查
来自题解:
上一个做法是先将元素插入到哈希字典中,然后再进行一轮遍历,查找想要的元素. 本做法是在插入元素的同时检查哈希字典中有无想要的值,如果有,就直接返回.

class Solution { public: vector twoSum(vector& nums, int target) {unordered_map m; for(int i = 0; i 0) { return vector{m[tmp],i}; } m[nums[i]] = i; } return vector{-1,-1}; } };

执行用时：12 ms, 在所有 C++ 提交中击败了90.15%的用户
内存消耗：9.9 MB, 在所有 C++ 提交中击败了13.00%的用户
错误思路