12/26 两数之和

1.两数之和

暴力法：

? ? ? ? 使用两个for循环，定义两个变量，i，j；i从0开始，j从1开始

? ? ? ? 注：nums.size()是获取数组元素的个数；

? ? ? ? c++，return{i，j}是一种返回多个值的语句，也被称为“解构返回”，创建一个包含两个元素的列表，并将两个元素返回！

????????

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

哈希表：

class Solution { // 定义一个名为Solution的类  
public:  
    vector<int> twoSum(vector<int>& nums, int target) { 
// 定义一个公共方法twoSum，接收一个整数数组nums和一个目标整数target  
        map<int,int> a; // 创建一个map（哈希表）a，用于存储数组元素及其索引  
        vector<int>b(2,-1); // 创建一个大小为2的向量b，并初始化为-1，用于存储找到的两个数的索引  
  
        for(int i=0;i<nums.size();i++) // 遍历数组nums  
        {  
            if(a.count(target-nums[i])>0) // 如果在map a中已经存在目标值target减去当前元素nums[i]的差值  
            {  
                b[0]=a[target-nums[i]]; // 那么差值对应的索引就是第一个数的索引，存入b[0]  
                b[1]=i; // 当前元素的索引i就是第二个数的索引，存入b[1]  
                break; // 找到答案后退出循环  
            }  
            a[nums[i]]=i; // 如果差值不存在于map a中，则将当前元素及其索引存入map a中  
        }  
        return b; // 返回向量b，其中包含找到的两个数的索引  
    };  
};

注释解释：

1. map<int,int> a;：这里使用map（哈希表）来存储数组元素及其对应的索引。map的键是数组元素，值是元素在数组中的索引。这样可以在常数时间内查找某个元素是否存在。
2. vector<int>b(2,-1);：初始化一个大小为2的向量b，并设置所有元素的值为-1。这个向量用于存储找到的两个数的索引。如果找不到符合条件的两个数，返回的就是这个初始化的向量。
3. for(int i=0;i<nums.size();i++)：遍历数组nums，对每个元素进行检查。
4. if(a.count(target-nums[i])>0)：这里检查map中是否已存在目标值target减去当前元素nums[i]的差值。如果存在，说明找到了两个数，它们的和等于目标值。
5. b[0]=a[target-nums[i]];?和?b[1]=i;：找到两个数后，将它们在数组中的索引分别存入向量b的两个位置。
6. break;：找到答案后退出循环，不再继续检查剩余的元素。
7. a[nums[i]]=i;：如果差值不存在于map中，将当前元素及其索引存入map，以便后续的查找。
8. return b;：最后返回存储了两个数索引的向量b。

?

?

?vector函数

在C++语言中，vector是一个动态数组模板类，它是C++标准模板库(STL)中的一个组件。vector提供了灵活的数组操作，例如插入、删除和访问元素等。它使用动态内存分配，可以在运行时自动增长或缩小，这使得它在处理大量数据或需要根据需求调整数组大小的情况下非常有用。

以下是一个简单的示例，展示了如何使用vector：

#include <iostream>  
#include <vector>  

int main() {
	// 创建一个空的整数向量  
	std::vector<int> vec;

	// 向向量中添加元素  
	vec.push_back(1);
	vec.push_back(2);
	vec.push_back(3);

	// 访问向量中的元素  
	for (int i = 0; i < vec.size(); i++) {
		std::cout << vec[i] << " ";
	}
	std::cout << std::endl;

	// 修改向量中的元素  
	vec[1] = 4;

	// 遍历并输出向量中的元素  
	for (int i = 0; i < vec.size(); i++) {
		std::cout << vec[i] << " ";
	}
	std::cout << std::endl;

	return 0;
}

在这个示例中，我们创建了一个空的整数向量vec，然后使用push_back对于vector容器来说，push_back函数在向容器尾部添加新元素时，会将新元素添加到现有元素的末尾。如果需要，它会自动重新分配内存以增加容器的大小。方法向其中添加元素。我们使用size方法获取向量的长度，并使用索引访问和修改向量中的元素。最后，我们使用循环遍历并输出向量中的所有元素。

map<int, int> a;??

是C++中STL（Standard Template Library）的一部分，用于声明一个map容器。

在这个声明中：

• map?是一个关联容器，它存储的元素是键值对（key-value pair）。
• <int, int>?表示这个map的键和值都是整数类型（int）。
• a?是这个map容器的变量名。

所以，map<int, int> a;?声明了一个名为?a?的map，其中键和值都是整数类型。

使用?<>?是模板的语法，它允许我们为容器或函数定义一个或多个类型参数。在这里，我们定义了两个类型参数，一个是键的类型（int），另一个是值的类型（int）。

至于为什么后面要加个?a，这完全取决于你自己的命名习惯。你可以使用任何合法的变量名。在这个例子中，我们选择了?a?作为这个map的名称。

vector<int> b(2, -1);?

在C++中，vector<int> b(2, -1);?创建了一个整数类型的向量（动态数组）b，并初始化了它。

具体来说：

1. vector<int>：表示这是一个整数类型的向量。
2. b：是向量的变量名。
3. (2, -1)：表示向量的初始化。这里，向量的大小为2，并且所有的元素都被初始化为-1。

所以，b?是一个大小为2的向量，其中的元素值都是-1。