1.什么時(shí)候會(huì)使用到哈希法？
思路：當(dāng)題意中需要判斷某個(gè)元素是否出現(xiàn)過(guò)，或者某個(gè)元素是否在這個(gè)集合里出現(xiàn)過(guò)。
2.例題：
給定一個(gè)整數(shù)數(shù)組 nums?和一個(gè)整數(shù)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出 和為目標(biāo)值 target??的那兩個(gè)整數(shù)，并返回它們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素在答案里不能重復(fù)出現(xiàn)。
你可以按任意順序返回答案。
示例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]解釋?zhuān)阂驗(yàn)?nums[0] + nums[1] == 9 ，返回 [0, 1] 。
3.題解文字說(shuō)明
使用哈希法的鍵值對(duì)可以使得時(shí)間復(fù)雜度和空間復(fù)雜度都是O(n)。使用一個(gè)新的集合map，map存放已經(jīng)遍歷過(guò)的元素，map.value存放已經(jīng)遍歷過(guò)元素的下標(biāo)，在原數(shù)組中順序遍歷查找map中是否存在target-nums[i]的值，如果不存在則將其nums[i]和他對(duì)應(yīng)的下標(biāo)i存入map中，如果存在，則找到結(jié)果，返回一個(gè)數(shù)組集合{map.value，i}
4.實(shí)現(xiàn)代碼
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
//非哈希算法
/*
for (int i = 0; i < nums.size() - 1; i++)
{
for (int j = i + 1; j < nums.size(); j++)
{
if (nums[i] + nums[j] == target)
{
return { i,j };
}
}
}
return {};
*/
//哈希算法
unordered_map<int, int>map;
for (int i = 0; i < nums.size(); i++)
{
// 遍歷當(dāng)前nums[i]元素，在map中尋找是否有與target-nums[i]的key
int s = target - nums[i];
auto iter = map.find(s);//auto用來(lái)推測(cè)map.find()的返回值類(lèi)型
if (iter != map.end())
{
return{ iter->second,i };
}
//沒(méi)找到匹配的key，則將其入到map哈希集合中
map.insert(pair<int, int>(nums[i], i));
}
return{};
}
};
int main()
{
Solution num;
vector<int> arr;
arr.push_back(2);
arr.push_back(7);
arr.push_back(11);
arr.push_back(15);
vector<int>x = num.twoSum(arr, 9);
cout << "[" << x[0] << "," << x[1] << "]" << endl;
}5.運(yùn)行結(jié)果
輸入：nums = [2,7,11,15], target = 9
輸出：[0，1]文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-720956.html
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-720956.html
到了這里，關(guān)于給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出 和為目標(biāo)值 target 的那兩個(gè)整數(shù)，并返回它們的數(shù)組下標(biāo)。（哈希法）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[雙指針] (三) LeetCode LCR 179. 查找總價(jià)格為目標(biāo)值的兩個(gè)商品 和 15. 三數(shù)之和](https://imgs.yssmx.com/Uploads/2024/02/744012-1.png)
![2023-06-12：如果一個(gè)正整數(shù)自身是回文數(shù)，而且它也是一個(gè)回文數(shù)的平方，那么我們稱(chēng)這個(gè)數(shù)為超級(jí)回文數(shù)。 現(xiàn)在，給定兩個(gè)正整數(shù) L 和 R （以字符串形式表示）， 返回包含在范圍 [L, R] 中](https://imgs.yssmx.com/Uploads/2024/02/480257-1.png)
