精选力扣500题第16题 LeetCode 1. 两数之和【c++详细题解】

骑猪看日落 2021-07-24 20:20 345阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路
         *  3、代码

### 1、题目 ###

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

**示例 1：**

输入：nums = [2,7,11,15], target = 9
    输出：[0,1]
    解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

**示例 2：**

输入：nums = [3,2,4], target = 6
    输出：[1,2]

**示例 3：**

输入：nums = [3,3], target = 6
    输出：[0,1]

**提示：**

*  `2 <= nums.length <= 103`
 *  `-109 <= nums[i] <= 109`
 *  `-109 <= target <= 109`
 *  **只会存在一个有效答案**

### 2、思路 ###

**(暴力枚举)**  O ( n 2 ) O(n^2) O(n2)

两重循环枚举下标`i,j`，然后判断 `nums[i]+nums[j]` 是否等于 `target`。

**(哈希表)**  O ( n ) O(n) O(n)

使用C++中的哈希表—`unordered_map<int, int> hash`

*  用哈希表存储前面遍历过的数，当枚举到当前数时，若哈希表中存在`target - nums[i]`的元素，则表示已经找到符合条件的两个数。
 *  若不存在`target - nums[i]`的元素则枚举完当前数再把当前数放进哈希表中

**时间复杂度:** 由于只扫描一遍，且哈希表的插入和查询操作的复杂度是  O ( 1 ) O(1) O(1)，所以总时间复杂度是  O ( n ) O(n) O(n).

### 3、代码 ###

/* 暴力写法 双重for循环 时间复杂度 O(n^2) class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int>res; for(int i=0;i<nums.size();i++) { for(int j=0;j<i;j++) { if(nums[i]+nums[j]==target) { res={j,i}; //记录答案 break; } } if(res.size()>0) break; } return res; } }; */
    /* 使用 unordered<int,int>hash; 使用hash表进行优化 建立key(元素)到value(下标)的映射 时间复杂度为O(n) */
    class Solution { 
    public:
        vector<int> twoSum(vector<int>& nums, int target)
        { 
            vector<int>res;
            unordered_map<int,int>hash;
            for( int i = 0; i < nums.size(); i++)
            { 
                int another = target - nums[i];
                if(hash.count(another))
                { 
                    res = { hash[another],i};
                    break;
                }
                hash[nums[i]] = i;
            }
            return res;
        }
    };

**原题链接：**[1. 两数之和][1.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

[1.]: https://leetcode-cn.com/problems/two-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/8ba900ef04d74388a5936e3b7a8f5e88.png