力扣刷题--每日一刷 1两数之和

Love The Way You Lie 2023-02-23 08:52 184阅读 0赞

题目出自 [力扣每日刷题之两数之和][Link 1]

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

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

**示例:**

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

**代码**

class Solution { 
    public:
        vector<int> twoSum(vector<int>& nums, int target)  //暴力解法
        { 
            for(int i =0; i< nums.size(); i++)
            { 
                for(int j = i+1; j< nums.size(); j++)
                { 
                    if(nums[i] + nums[j] == target)
                        return { i,j};
                }
            }
            return { };
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM3ODgwMA_size_16_color_FFFFFF_t_70]

[参考的优秀解法：一遍哈希][Link 2]

class Solution { 
    public:
        vector<int> twoSum(vector<int>& nums, int target) { 
    
            unordered_map<int,int> m;
            
            for(int i = 0; i < nums.size(); i++)
            { 
                if(m.find(target-nums[i]) != m.end())      //m中存在对应的键值
                    return { m[target-nums[i]], i};        
                // m[target-nums[i]]为已经加入map的元素的索引，所以小于本轮循环中的i，放在前面
    
                m[nums[i]] = i;       //向map中添加元素
            }
            return { };
        }
    };

[Link 1]: https://leetcode-cn.com/problems/two-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM3ODgwMA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200706211007701.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM3ODgwMA==,size_16,color_FFFFFF,t_70
[Link 2]: https://leetcode-cn.com/problems/two-sum/solution/c-san-chong-fang-fa-jian-dan-yi-dong-ji-bai-100-z-/