感謝各位大佬對我的支持,如果我的文章對你有用,歡迎點擊以下鏈接
🐒🐒🐒 個人主頁
🥸🥸🥸 C語言
🐿?🐿?🐿? C語言例題
🐣🐣🐣 python
🐓🐓🐓 數據結構C語言
🐔🐔🐔 C++
🐿?🐿?🐿? 文章鏈接目錄
🏀🏀🏀 筆試練習題
🐯🐯🐯 Git
🚀🚀🚀 leetCode熱題100

兩數之和

兩數之和鏈接

題目解析

這道題其實就是讓我們在給定的數組中找出兩個數,讓他們相加的和等于給定的值,但是要注意兩個數字是不可以相等的,所以如果遇到相等的數字就應該舍去

這道題給出兩種解法
第一種是暴力求解,第二種是哈希

方法一暴力求解

暴力解法其實就是給兩層循環

先用一個count去記錄要相加等于的數字
第一次for循環先讓count減去 i 位置的數字

第二層for循環就去找count減去后的值,如果第二層for循環沒有找到對應的值,那么就重新讓count等于給定的值,然后 i 往后移

之后重復之前的操作
當遇到 i + j 的值為count時要判斷他們 i 和 j 是否指向的是同一個位置,如果位置不同但是值相等的我們也要舍去

如果位置不同,且值也不同那么就可以將 i 和 j 的值push_back進一個數組中

代碼

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> arr;int count = target;for (vector<int>::iterator it1 = nums.begin(); it1 != nums.end(); it1++){count = count - (*it1);for (vector<int>::iterator it2 = nums.begin(); it2 != nums.end();it2++){if (*it2 == count&&it1!=it2) {arr.push_back(it1 - nums.begin());arr.push_back(it2 - nums.begin());break;}}count = target;if(arr.size()>0)break;}return arr;}
};

方法二哈希

下面的代碼我也有點看不懂
我來說說我的想法
就是遍歷一遍數組,然后將出現的數字存儲在一個哈希表中,哈希表是記錄數字出現的次數

比如target為10,那么我們在給定的數組中的第一個元素是1,后面我們就在哈希表中查找9這個元素是否存在
可以從上圖中看到,哈希表中9存儲的是1,說明有一個元素的值是9,因此就查找成功了

代碼

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hashtable;for (int i = 0; i < nums.size(); ++i) {auto it = hashtable.find(target - nums[i]);if (it != hashtable.end()) {return {it->second, i};}hashtable[nums[i]] = i;}return {};}
};