一，题目描述

这里直接贴的leetcode中的题目（哈哈哈）；

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

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

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

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

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

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

这里有三个案例。。。

二，算法思路

毫无疑问，，对于一般解法，，，我们肯定会遍历两边数组，，，来一个一个找，，对于第一个循环的遍历，，是没有方法去除的，，，所以，，想要优化算法只能降低查找的时间复杂度，，这里就用的哈希表来降低查找的时间复杂度。。

这里先说明一下，这里的解法只代表了我自己的思路，关于**“两数之和”**的一般解法，大家如果有需要的话可以看看其他博主的文章，这里只讲一下效率比较高的哈希表解法。。。。哈哈哈

1，哈希表的相关说明

哈希表是数据结构的一种，是一种散列表，，，这种结构更加便于数据的查找，查找速度会更加快，，，

但是，显而易见的是，虽然哈希表会让算法的时间复杂度更小，但是占用的空间会更多，，，就比如这题，，，用一般解法的话，时间复杂度是O(n²)，空间使用是O(1)， ，，但使用哈希表之后时间复杂度变为O(n)， 空间复杂度变为O(n)。。。典型的空间换时间解法。。。

因此，哈希表还是比较吃空间的。。。哈哈。。

2，哈希算法

在讲哈希算法之前，不知道大家有没有了解过，，，桶排序，，，在我看来，桶排序也是哈希表的一般应用，，对于一般的排序，，，无论是快排，归并排序。。。或者其他排序算法。。都是通过两两交换将特定的元素换到前面，，，，但是桶排序，，不一样，，，下面先给出例子，，，

将数组里面的所存的值，，，变为上标，，然后变为一个判定数组，，，如果原输入的数组中存在这个值，，，就将这个数值对应出现的次数一。。。

如图，，这里面就差不多是桶排序，，，这里选的数值比较小，，可知在数据范围不是很大的情况下，，，用这种排序所得的时间复杂度就是O(n)的，，不过用到了辅助空间。。。。

而在数据范围很大，，，而输入范围不是很大的。。。情况下怎么解决呢？，，，就比如设置的数值范围为10⁹，而数据的总数不过10^4，，，这样的话前面的桶排序的用发，，，就不是特别好使了，，，因为消耗的空间实在是太大了，，，这时候就出现了哈希函数，，，，

哈希函数，，，按照我的理解就是，，通过一个函数将，，，输入的值转化为一个数组上标，，，在将这个值存在其中，，，下面针对这个题目举个例子：

如图，，先开辟一个数组，，大小的话大于取模值就行，，，不要问我为什么，动动你聪明的脑瓜想想，，这里面的编号我没排序，，感觉这样的话会更清晰，，，这样的话在查找的时候，，，直接对查找值取模就可以得到相应的答案。。。

这样就的话就可以将数值的范围变为输入值的数目

但是，，这里还有一个问题，，当出现两个数取模的得到的值相同怎么办？，，，这就是哈希算法中的数据冲突问题，，那如何解决冲突问题呢？？这里只提供一个方法，，，毕竟讲题解，，不是讲哈希表，，哈哈，，如下图：

这里面的输入值对10007取模得到的值都是3245，，，所以不可能将全部的值都加到3245上，，，因此我们我们将冲突的数值向后移，，，也就是出现冲突的值，，全部向后移，，直到不出现冲突为止，，，这是解决冲突的一种方法，，还有很多其他的方法，，，大家感兴趣可以去搜搜，，，

还有，，选取的，，取模的，，数值的最好是素数，，这个是通过数学证明得来的最能降低数组冲突的方式，，，大家感兴趣可以去搜搜，，，

3，题目讲解

先画个流程图，，，

如图，，这题相对还是比较简单的，，求两数之和，，无非就是，，对每一个数看看是否有另一个数与其相加能得到，，，目标值，，

这里主要是构建哈希表，，，

1、对于每一个输入值，，先将目标值与其的差值处理到哈希表中，，

2、在对于每一个输入值，，通过哈希表的查找，，看看是否能找到这个输入值，，找到这个输入值，，就代表有差值与这个值相等，，，也就代表有其他的输入值也这个相加等于目标值。。下面就是代码，，，

三，题解代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        const int N = 100007; //对于数据范围,这是10000以上的最小的素数
        const int INF = 0x3f3f3f3f;

        int judge[N];//定义的哈希表
        int judge1[N];//这个表存的是对应的元数组的下标
        memset(judge, INF, sizeof(judge));//初始化
        memset(judge1, INF, sizeof(judge));
        
        vector<int> res;
        //第一步：将每个元素的被减值存入到哈希表中
        for (int i = 0; i < nums.size(); i++)
       {
       //这部处理稍微看看，a是代表的寻找的哈希表中的数组编号，。，想想为什么这么写，，，
        int a = ((target - nums[i] ) % N + N) % N;
        while (judge[a] != INF) { a++, a %= N; }
        judge[a] = target - nums[i];
        judge1[a] = i;
       }
     //第二步：对于每个元素，看看哈希表中出现该值
    for (int i = 0; i < nums.size(); i++)
    {
        int t = 0;
        int a = ((nums[i] ) % N + N) % N;
        while (judge[a] != INF)
        {
            if (judge[a] == nums[i] && i != judge1[a])
            {
               res.push_back(i);
               res.push_back(judge1[a]);
                t = 1;
                break;
            }
            a ++;
            a %= N;
        }
        if (t) break;
    }
        return res;
    }
};

这是leetcode的代码，，，

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100007;
const int INF = 0x3f3f3f3f;

int judge[N] ;
int judge1[N];

int nums[N];
int target;
int n;

int main()
{
    cin >> n >> target;
    memset(judge, INF, sizeof(judge));
    for (int i = 0; i < n; i++) cin >> nums[i];

    for (int i = 0; i < n; i++)
    {
        int a = ((target - nums[i] ) % N + N) % N;
        while (judge[a] != INF) { a++, a %= N; }
        judge[a] = target - nums[i];
        judge1[a] = i;
    }

    for (int i = 0; i < n; i++)
    {
        int t = 0;
        int a = ((nums[i] ) % N + N) % N;
        while (judge[a] != INF)
        {
            if (judge[a] == nums[i] && i != judge1[a])
            {
                cout << i << ' ' << judge1[a];
                t = 1;
                break;
            }
            a ++;
            a %= N;
        }
        if (t) break;
    }
    return 0;
}

这是自己用vs写的，，，跟上面的差不多，，，代码写的比较烂，，哈哈，，还望各位读者能自己多多完善，，，

四，运行结果以及最后的一点点解释，，

一点点解释，，，我四舍五入一下等于没解释，，不过分吧，，哈哈，，（这第四点其实实在水字数） 咳咳，，，