简单题：1.两数之和

题目描述：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 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]

解答：

方法一、暴力枚举：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        int result_i=0,result_j=0;
        for(int i=0;i<nums.size();++i){
            for(int j=0;j<nums.size();++j){
                if(nums[i]+nums[j] == target && j!=i){
                    result_i = i;
                    result_j = j;
                    break;
                }
            }
        }
        std::vector<int> result;
        result.push_back(result_i);
        result.push_back(result_j);
        return result;
    }
};

方法二、哈希表:

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 {};
    }
};

哈希表的特性：

(1)查找时复杂度为O(1)；

(2)使用insert插入元素时，第一次insert成功，第二次insert不能将第一次的值覆盖；

(3)使用索引赋值时，能将元素进行有效更新。

例：

#include<unordered_map>

// 初始 map 的内容为{{1，1}，{2，2},{3,3}}
unordered_map<int, int> map{{1,1},{2,2},{3,3}};
//修改第3个元素
map[3]=4;
// map的内容更新为{{1，1}，{2，2},{3,4}}
// 插入新元素
map.insert({4,10});
// map的内容更新为{{1，1}，{2，2},{3,4},{4,10}}
// 试图修改map第4个元素的值
map.insert({4,20});
// map的内容仍为{{1，1}，{2，2},{3,4},{4,10}}

原文地址：https://blog.csdn.net/qq_43685921/article/details/144310696

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！