文章目錄

• • 1. 題目
  • 2. 解題
  • • 1. 暴力解法
    • 2. 哈希法
    • 3. python3解答

1. 題目

題目鏈接：https://leetcode-cn.com/problems/two-sum/

給定一個整數數組 nums 和一個目標值 target，請你在該數組中找出和為目標值的那 兩個 整數，并返回他們的數組下標。

你可以假設每種輸入只會對應一個答案。但是，你不能重復利用這個數組中同樣的元素。

給定 nums = [2, 7, 11, 15], target = 9因為 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

---

2. 解題

1. 暴力解法

每個元素都跟后面的比較，n² 復雜度

class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {int i,j;vector<int> ans;for(i = 0; i < nums.size()-1; ++i){for(j = i+1; j < nums.size(); ++j){if(nums[i]+nums[j] == target){ans.push_back(i);ans.push_back(j);return ans;}}}return ans;} };

2. 哈希法

利用unordered_map哈希查找，先建立哈希表O(n)，再查找O(n)

//哈希法 class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {int i, d;vector<int> ans;unordered_map<int,int> unomap;//unordered_map是哈希表for(i = 0; i < nums.size(); ++i)//建立哈希表unomap[nums[i]] = i;//哈希數組下標是值，存的原來的下標for(i = 0; i < nums.size(); ++i){d = target - nums[i];if(unomap.find(d) != unomap.end() && unomap[d]>i){//如果查找到了，且不是同一個元素ans.push_back(i);ans.push_back(unomap[d]);break;}}return ans;} };

• 優化，只需要一次遍歷

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

3. python3解答

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:dic = {}for i in range(len(nums)):dic[nums[i]] = ifor i in range(len(nums)):if (target-nums[i]) in dic and dic[target-nums[i]] > i:return [i,dic[target-nums[i]]]return [-1,-1]

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1. 两数之和（哈希）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。