1.两数之和

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

leecode两数之和

• 认知错误
• 一、C解法（暴力求解）
• 二、C++（哈希表）
• • 1.查找表法介绍
  • 2.思路
• 总结

---

认知错误

文章给出的int* returnSize自然而然认为成了最后要返回的return，实际上这个是传进来的参数，应该自己填充赋值为2；没有理解输入格式导致的困惑。

一、C解法（暴力求解）

参考别人题解思路代码：

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int *p=NULL;
    p = (int*)malloc(sizeof(int)*2);
    *returnSize=2;//这个是限定条件，不然调用这个函数用不了
    for(int i=0;i < numsSize-1;i++){
        int j = 1,flag =0;
        for(j=i+1;j<numsSize;j++){
            if(nums[i]+nums[j]==target)
            {
                p[0]=i;
                p[1]=j;
                flag =1;break;
            }
        }
        if(flag ==1){
            break;
        }
    }
    return p;
}

但这种方法低效，时间复杂度：O(N^2)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。空间复杂度仅O(1)，因为只用到了常数个临时变量。
在算法优化中，这种时间复杂度和空间复杂度的组合，思路通常以空间换时间。

二、C++（哈希表） 1.查找表法介绍

1. 在遍历的同时，记录一些信息，以省去一层循环，即“以空间换时间”
2. 需要记录的数值是已经遍历过的数值及对应的下标，可以借助查找表实现
3. 查找表两种实现：哈希表；平衡二叉搜索树（需要维护查找表中元素顺序性时使用）

2.思路

使用哈希表快速寻找数组中是否存在目标元素，存在则找出索引。
创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。代码如下（示例）：

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        unordered_map hashtable;
        for(int i=0;ifirst 表示的是这个元素的key的值；
            it->second 表示的是这个元素的value的值。
            */
            auto it=hashtable.find(target-nums[i]);//查找函数，通过key查找一个元素，返回迭代器类型
            if(it != hashtable.end()){//哈希表中找到匹配的元素
                return {it->second,i};//返回两个下标
            }
            hashtable[nums[i]]=i;//无匹配则哈希表中填入nums[i]对应的下标i
        }
        return {};
    }
};

时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1)地寻找 target - x。
空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。

---

总结

还得是用一些结构啊，C语言不靠谱，优化版的算法看不懂