Leetcode 1

题目描述

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

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

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

题解

暴力解法

#include 
#include 
#include 
using namespace std;
 
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i=0;isize();i++)
        {
            for(int j=i+1;jsize();j++)
            {
                if(nums[i]+nums[j]==target)
                {
                    return{i,j};  //注意若return vector值要用{}
                }
            }
        }
        return {};  //return时vector若空要用{}
    }
};

时间复杂度为O（n^2）,空间复杂度为O（1）

哈希解法

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

 时间复杂度为O（n）,空间复杂度为O（n）

分析： 

unordered_map<int, int> hashtable; //定义一个无序的哈希表
 
在C++中，unordered_map 是一个无序的哈希表实现，
它允许我们存储键值对，并且能够快速地根据键来查找对应的值。

键（Key）和值（Value）是一种常见的数据结构，特别是在字典（或哈希表、映射）中。键和值之间的关系是一一对应的，每个键都唯一地对应一个值。

怎么确定谁是键谁是值？ 

1. 唯一性：键通常是唯一的，而值可以是重复的。这意味着你可以使用键来快速查找、添加、修改或删除与之关联的值。

2. 查找效率：键用于快速查找对应的值。在一个优化良好的哈希表中，查找一个键对应的值通常是一个常数时间操作（O(1)）。

3. 数据表示：键和值的具体含义取决于你正在处理的数据。例如，在一个电话本应用中，键可能是人名（用于快速查找），而值可能是与该人名关联的电话号码。

4. 业务需求：在业务逻辑中，键和值的选择通常基于你的业务需求。例如，如果你需要快速检索数据，那么将检索条件作为键，返回的结果作为值是很自然的选择。

5. 数据模型：在数据库或数据模型中，键通常用于唯一标识一条记录，而值则表示该记录的其他属性。

 由此可以判断，nums数组中的数是键，下标是值

auto it = hashtable.find(target - nums[i]);
 
target-nums[i]表示查找哈希表中对应这个数（nums[i]的补数）的下标
it是一个迭代器

if (it != hashtable.end()) { //如果it没有到哈希表的末尾，说明找到了这个键
      return {it->second, i};  //那么就返回键对应的值，也就是下标
 }
hashtable[nums[i]] = i;  //如果没找到这个键，就把它加到哈希表里，以便后续查找

一些语法提示： 

 在C++的std::unordered_map中，每个元素都是一个键值对（key-value pair）。当你使用迭代器（如it）来遍历或查找哈希表中的元素时，迭代器指向的是一个包含两个成员的std::pair对象，这两个成员分别是first和second。

• it->first：代表键（key），即你存储在哈希表中的整数值。
• it->second：代表值（value），即与键相关联的数据，在这个例子中，值是与数组中的整数对应的下标。

---

 题解来源：

作者：力扣官方题解
链接：https://leetcode.cn/problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/