LeetCode：1. Two Sum

[lefex]

#include <stdio.h>
#include <vector>
#include <unordered_map>

using namespace std;
using std::unordered_map;

/**
 【题目】
 给出一个整形数组和一个目标值，找出数组中，两个成员的和是目标值所在数组中的下标。
 你可以假定每次输入只对应一种答案，且不能使用数组中同样的元素。
 
 【审题】
 题中要求：
 1.给定一个数组和一个目标值，假如数组为 nums = [2, 7, 11, 15], 目标值为：target = 9
 2.找出目标值 9 是数组 nums 中哪两个元素的和
 3.返回找到元素的下标，比如 return [0, 1].
 
 【举例】
 Given nums = [2, 7, 11, 15], target = 9,
 
 Because nums[0] + nums[1] = 2 + 7 = 9,
 return [0, 1].
 
 【方法】
 1. 两次遍历找到和为 target 的两个元素
 2. a.使用一个unordered_map用来保存 nums 中元素和它的下标
    b.每次查找找到 target - nums[i] 的差值，查找就是下一个要找的元素
 */

/**
 【C++向量 Vector】
 向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。
 跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组
 */
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target);
    vector<int> twoSum2(vector<int>& nums, int target);
};

/**
 nums = [2, 7, 11, 15], target = 9
 两次遍历找到和为 target 的两个元素
 时间复杂度为：O(n*n)
 空间复杂度为：
 
 Runtime: 124 ms, faster than 37.43% of C++ online submissions for Two Sum.
 Memory Usage: 9.6 MB, less than 62.01% of C++ online submissions for Two Sum.
 */
vector<int>  Solution::twoSum(vector<int> &nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
        int fnum = nums[i];
        for (int j = i+1; j < nums.size(); j++) {
            int snum = nums[j];
            if (fnum + snum == target) {
                return {i, j};
            }
        }
    }
    return vector<int>();
};

/**
 1.使用一个unordered_map用来保存 nums 中元素和它的下标
 2.每次查找找到 target - nums[i] 的差值，查找就是下一个要找的元素
 
 Runtime: 12 ms, faster than 97.81% of C++ online submissions for Two Sum.
 Memory Usage: 10.4 MB, less than 33.11% of C++ online submissions for Two Sum.
 */
vector<int> Solution::twoSum2(vector<int> &nums, int target) {
    unordered_map<int, int> record;
    for (int i = 0; i < nums.size(); i++) {
        int sub = target - nums[i];
        if (record.find(sub) != record.end()) {
            // 找到了
            return {record[sub], i};
        } else {
            record[nums[i]] = i;
        }
    }
    return vector<int>();
};