江苏龙网

  1. 首页 > 人文 > >

vivo|LeetCode 1. 两数之和

vivo|LeetCode 1. 两数之和


题目描述

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

题解
备注:没有进行输入检查默认是有效输入数据.
暴力双重循环
最简单的一下子想到的双重循环遍历查找第一层i:begin->end第二次j:i+1->end
class Solution {public:    vector<int> twoSum(vector<int>& 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<int>{ij;                            return vector<int>{-1-1;    ;
执行用时：460 ms 在所有 C++ 提交中击败了39.91%的用户
内存消耗：8.9 MB 在所有 C++ 提交中击败了36.09%的用户
思考一下使用双重循环时间复杂度应该是在O(n^2).
哈希字典
稍加思索感觉这种有查找的可以使用哈希字典来提升下速度.
思路如下: 1. 遍历一次数组将其填充到哈希字典中key为数组值value为数组下标.如果有重复的元素只会记录最后一次出现的索引. 2. 遍历一次数组查找相应值要注意遍历时候的数组索引和.
class Solution {public:    vector<int> twoSum(vector<int>& nums int target) {        unordered_map<intint> m;        for(int i = 0;i<nums.size();i++)        {            m[nums[i

=i; // key:nums[i
value:i                for(int i = 0;i<nums.size();i++)        {            int tmp = target - nums[i
;            if(m.count(tmp) > 0 && m[tmp
 != i)            {                return vector<int>{im[tmp
;                                        return vector<int>{-1-1;    ;
执行用时：16 ms 在所有 C++ 提交中击败了75.88%的用户
内存消耗：9.9 MB 在所有 C++ 提交中击败了10.90%的用户
从执行时间来看应该还是有更好的解法.稍加思索没想出来看下题解.
哈希字典插入时检查
来自题解:
上一个做法是先将元素插入到哈希字典中然后再进行一轮遍历查找想要的元素. 本做法是在插入元素的同时检查哈希字典中有无想要的值如果有就直接返回.
class Solution {public:    vector<int> twoSum(vector<int>& nums int target) {        unordered_map<intint> m;        for(int i = 0;i<nums.size();i++)        {            int tmp = target - nums[i
;            if(m.count(tmp) > 0)            {                return vector<int>{m[tmp
i;                        m[nums[i

 = i;                return vector<int>{-1-1;    ;
执行用时：12 ms 在所有 C++ 提交中击败了90.15%的用户
内存消耗：9.9 MB 在所有 C++ 提交中击败了13.00%的用户
错误思路

  1. 【vivo|LeetCode 1. 两数之和】第一想法是排序然后再进行查找但是结果不对然后才反应过来排序后数组的下标变化了.(可以做一个新的数据结构把value和索引下标包装起来排序后就不会丢失索引信息.)


    推荐阅读


    上一篇：远东宏信：公司在任何时间未偿还票据及永续证券的面额总值最高为40亿美元

    下一篇：从北斗星通看北斗产业链的投资机会