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

执行用时：460 ms, 在所有 C++ 提交中击败了39.91%的用户 内存消耗：8.9 MB, 在所有 C++ 提交中击败了36.09%的用户

思考一下,使用双重循环,时间复杂度应该是在O(n^2).

哈希字典

稍加思索,感觉这种有查找的,可以使用哈希字典来提升下速度.

思路如下:

遍历一次数组,将其填充到哈希字典中,key为数组值,value为数组下标.如果有重复的元素,只会记录最后一次出现的索引.遍历一次数组,查找相应值,要注意遍历时候的数组索引和.class Solution {

执行用时：16 ms, 在所有 C++ 提交中击败了75.88%的用户 内存消耗：9.9 MB, 在所有 C++ 提交中击败了10.90%的用户

从执行时间来看,应该还是有更好的解法.稍加思索,没想出来,看下题解.

哈希字典,插入时检查

来自题解:

上一个做法是先将元素插入到哈希字典中,然后再进行一轮遍历,查找想要的元素. 本做法是在插入元素的同时检查哈希字典中有无想要的值,如果有,就直接返回.

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

错误思路

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