1、題目

給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素不能使用兩遍。

2、思考分析

雙for循環(huán)的時(shí)間復(fù)雜度O(n^2)，而哈希法的時(shí)間復(fù)雜度為O(1),所以哈希法顯然更有效。
這里我們使用map而不使用set、或者自構(gòu)造數(shù)組。
數(shù)組與set的局限：

1、數(shù)組大小受到限制，如果元素較少，而哈希值太大會(huì)造成內(nèi)存空間浪費(fèi)
2、set是一個(gè)集合，里面放的元素只能是一個(gè)key，不能知道key所在的位置，也就是說我們只能知道key是否存在。
而這一題不經(jīng)要判斷y是否存在還要疾苦y的下標(biāo)。
3、使用map可以同時(shí)保存key、value，類似于數(shù)組。我們可以用key保存數(shù)值，用value保存數(shù)值所在下標(biāo)。

C++中map的有關(guān)用法可以參考這篇筆記:STL容器及其簡單應(yīng)用
這里我們選擇unordered_map;
需要注意map.insert函數(shù)的用法;

map.insert(pair<int, int> (nums[i], i));

3、哈希法

class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();unordered_map<int,int> map;for(int i=0;i<n;i++){auto iter = map.find(target-nums[i]); //觀察是否找到另外一個(gè)數(shù)//如果找到了if(iter !=map.end()){//iter.first:key iter.second:下標(biāo)return {i,iter->second};}map.insert(pair<int, int> (nums[i], i));}return {};} };

總結(jié)

以上是生活随笔為你收集整理的leetcode 1. 两数之和 思考分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。