1.两数之和[easy]

LeetCode 算法题停止更新，请移步至 GitHub。

题目描述

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

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

示例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题方法

1.暴力法

两次遍历，查找 nums[i] + nums[j] == target 的值并放入数组返回。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i=0; i<nums.size(); i++) {
            for (int j=i+1; j<nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    vector<int>a;
                    a.push_back(i);
                    a.push_back(j);
                    return a;
                }
            }
        }
        throw "error";
    }
};

状态	执行用时	内存消耗
通过	224 ms	9.3 MB

时间复杂度：O(n^2)

空间复杂度：O(1)

2.哈希表

使用一遍循环，在循环的过程中，把数组中的符合条件的 complement 与哈希表中的 Key 相比较，如果存在，则取出哈希表中对应的 Value 和当前的下标放入 vector 中。

然后把数组中的值作为 Key，下标作为 Value 存入哈希表中。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        vector<int> a;
        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i];
            if (map.find(complement) != map.end()) {
                a.push_back(map[complement]);
                a.push_back(i);
                return a;
            }
            map[nums[i]] = i;
        }
        return a;
    }
};

状态	执行用时	内存消耗
通过	16 ms	10.1 MB

时间复杂度：O(n)

空间复杂度：O(n)