1,两数之和/数组与字符串

两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解法1：暴力循环

对每个数都从头开始寻找是否前面有和为target的数
时间复杂度：O(n²)，对每个数都试图历遍一次数组寻找答案。
空间复杂度：O(1)，并不需要保存啥·······
代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<vector<int>> s;
        vector<int> a;
        for (int i = 1; i < nums.size(); i++) {

            for (int j = 0; j < i; j++) {
                if (nums[i] + nums[j] == target) {
                    a.push_back(j);
                    a.push_back(i);
                    return a;
                }

            }

        }
            return a;

        }
};

解法2：哈希表

每个数都尝试从之前已经插入到的哈希表里的数中寻找目标数，没有的话就将当前数与序号插入哈希表。跟上面的解法1相比可以说空间换时间。
时间复杂度：O(n)，只对每个数循环一次，哈希表查找复杂度是常数。
空间复杂度：O(n)，保存哈希表
代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        vector<int> a;

        unordered_map<int, int> s;
        for (int i = 0; i < nums.size(); i++) {
            int tmp = target - nums[i];
            unordered_map<int, int>::iterator iter;
            iter = s.find(tmp);
            if (iter != s.end() && iter->second != i) {
                a.push_back(i);
                a.push_back(iter->second);
                return a;
            }
            s.insert(pair<int, int>(nums[i],i));
        }
    
        return a;

    }
};