1.两数之和 - 力扣

力扣算法题Day1

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

1
2
3

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1 2	输入：nums = [3,2,4], target = 6 输出：[1,2]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？

方法1：

1. 暴力循环法

遍历每个元素x，并依次往后查找是否存在一个值与target - x相等。代码示例如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int x = 0;
        int y = 0;
        vector<int> index;
        for (int i = 0; i < nums.size(); i++) {
            x = nums[i]; // 获取第i个元素
            for (int j = i + 1; j < nums.size(); j++) {
                y = nums[j]; // 获取第j个元素
                if (x + y == target) {
                    index.push_back(i);
                    index.push_back(j);
                    break;
                }
            }
        }
        return index;
    }
};

算法复杂度分析：
时间复杂度：O(n^2)，空间复杂度：O(1)
对于每个元素，通过遍历数组寻找所对应的目标元素，这将耗费 O(n) 的时间，因此时间复杂度为 O(n^2)。

2. 两遍哈希表

先将每个元素装入哈希表中，然后循环去查找每个元素x的对应目标元素（target-x）是否在表中，还要注意目标元素不能是元素本身。

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

算法复杂度分析：
时间复杂度：O(n)，空间复杂度：O(n)
包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1) ，所以时间复杂度为 O(n)。
所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素，所以空间复杂度为 O(n)。

3.一遍哈希表

在进行将元素插入到表中的同时，同时检查表中是否已经存在当前元素所对应的目标元素。

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