1. 两数之和

题目描述

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

自解_暴力法

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

• 与官方题解1类似，暴力法
• 时间复杂度：\(O(n^2)\)，对于每个元素，试图通过遍历数组的其余部分来寻找它所对应的目标元素。
• 空间复杂度：\(O(1)\)

注意

1. error: control reaches end of non-void function：控制到达非void函数的结尾。即本应带有返回值的函数到达结尾后可能并没有返回任何值

   本题中有可能找不到目标值，所以需要在循环检测外也返回一个值，否则会出现此错误

2. 想要返回vector时，如果是在调用函数内部创建的vector，会出问题。解决方法：将需要返回的vector引用值作为参数传进函数，在函数内部使用引用。而函数类型设置为bool

   参考：https://www.cnblogs.com/pengjun-shanghai/p/4913409.html

参考官方题解_map

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> index;
        vector<int> ans(2);
        for (int i = 0; i < nums.size(); i++){
            if (index.find(target - nums[i]) != index.end()){
                ans[0] = index.find(target - nums[i]) -> second;
                ans[1] = i;
                return ans;
            }
            else{
                index.insert(pair<int,int>(nums[i],i));
            }
        }
        return ans;
    }
};

• 时间复杂度：\(O(n\log(n))\)，我们将元素与索引放入map，利用map进行查找。但由于C++的map是基于红黑树实现的，查找的时间复杂度约为\(\log(n)\)，所以时间复杂度为 \(O(n\log(n))\)。

• 空间复杂度：\(O(n)\)，所需的额外空间取决于map中存储的元素数量，该表中存储了 \(n\) 个元素，但C++的map基于红黑树实现，该树的一个节点在不保存数据时，占用16字节的空间，包括一个父节点指针，左右孩子指针，还有一个枚举值(标示红黑的，相当于平衡二叉树中的平衡因子)，可见，map还是很耗内存的。

  参考：https://www.cnblogs.com/shijingjing07/p/5588578.html

注意

此题中官方题解使用的是哈希表，如果使用hash_map可以将查询复杂度降低到\(O(1)\)，从而使得整体复杂度为\(O(N)\)，但是hash_map不是标准的C++库，没有办法提交题解。

参考：https://www.cnblogs.com/codernie/p/9180361.html#jump1

LeetCode_#1_两数之和_C++题解

原文：https://www.cnblogs.com/whale90830/p/10515876.html