LeetCode刷题（54）～两数之和【暴力循环/双哈希/单哈希】

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解答 By 海轰

提交代码（暴力循环）

vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> a(2);
        for (int i=0;i<nums.size()-1;i++)
        for (int j=i+1;j<nums.size();j++)
        if (nums[i]+nums[j]==target)
        {
             a[0]=i;
             a[1]=j;
             break;
        }
        return a;
    }

运行结果

提交代码（双哈希）

vector<int> twoSum(vector<int>& nums, int target) {
       unordered_map<int,int> m;
       m[nums[0]]=0;
       vector<int> a;
       for(int i=1;i<nums.size();++i)
       {
           if(target-nums[0]==nums[i])
           {
             a.push_back(0);
             a.push_back(i);
             return a;
           }
           m[nums[i]]=i;
       }
       for(int i=1;i<nums.size();++i)
       {
           if((m[target-nums[i]]!=i)&&m[target-nums[i]])
           {
               a.push_back(i);
               a.push_back(m[target-nums[i]]);
               break;
           }
       }
       return a;
    }

运行结果

提交代码（一次哈希）

vector<int> twoSum(vector<int>& nums, int target) {
       unordered_map<int,int> m;
       for(int i=0;i<nums.size();++i)
       {
           int temp=target-nums[i];
           if(m.find(temp)!=m.end())
           return {m[temp],i};
           m[nums[i]]=i;
       }
       return {};
    }

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum