Day 14 - 1. two sum

Day14 - 1.两数之和

LeetCode 1.两数之和

题目链接：

https://leetcode.cn/problems/two-sum/

1. 题目描述

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

举个例子：

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

2. 思路解析

首先暴力的方法就不说了，比较简单但是时间复杂度比较高。

这里讲一种空间换时间的方法，利用hash表，提前把nums中的元素nums[i]作为hash表的key主键，nums的索引作为hash表的value值存到hash表中。

这样我们只需要遍历nums，在hash表中寻找target-nums[i]，如果target-nums存在hash表中，且hash[target-nums] != i，那么就返回{i,hash[target-nums]}。如果遍历完整个nums都没有任何结果返回，就说明没有找到。

3. C++代码

3.1.1. 暴力

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        for(int i = 0; i < nums.size(); i++)
        {
            // 内层循环从 i+1 开始
            // 因为前面 i-1 个元素已经验证过不匹配（且不能为自身）
            for(int j = i+1; j < nums.size(); j++)
            {
                if(nums[i] + nums[j] == target)
                {
                    return {i, j};
                }
            }
        }
        return {};
    }
};

用空间换时间的方法。

首先a + b = target，看似a, b都是未知数变量，需要遍历。但其实由于target是个常数，我们可以固定a值，而遍历b值，这样就可以使得复杂度降为O(n)。利用hash表查询元素的O(1)特性。

3.1.2. 哈希双循环

unodered_map容器方法：.end() 返回指向容器中最后一个键值对之后位置的正向迭代器。

用法：it!=mymap.end()

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        unordered_map<int, int> u_map;
        int nums_len = nums.size();
        // 预生成 hashmap
        for(int i = 0; i < nums.size(); i++)
        {
            u_map[nums[i]] = i;
        }
        //查询由nums所有元素生成的hashmap
        for(int i = 0; i < nums_len; i++)
        {
            int clm = target - nums[i];
            if(u_map.find(clm) != u_map.end() && u_map[clm] != i)
            {
                return {i, u_map[clm]};
            }
        }
        return {};
    }
};

上面的方法我们需要预先生成hash表，这样就会遍历两次nums，那么能否只遍历一遍nums呢？对于nums[i]，我们只需要把每次查询由nums中所有元素组成的hash表，修改为每次查询由nums[0]~nums[i-1]组成的hash表，其实效果是一样的。

3.1.3. 哈希单循环

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        unordered_map<int, int> pre_map;
        int nums_len = nums.size();
        // 不用预生成 hashmap
        // 查询由nums所有元素生成的hashmap
        for(int i = 0; i < nums_len; i++)
        {
            int clm = target - nums[i];
            if(pre_map.find(clm) != pre_map.end() && pre_map[clm] != i)
            {
                return {i, pre_map[clm]};
            }
            else
            {
                pre_map[nums[i]] = i;
            }
        }
        return {};
    }
};

4. 复杂度分析

时间复杂度： 只需要遍历一遍nums，每次查hash表的时间复杂度是O(1)，故整体的时间复杂是O(n)，其中n为nums的长度。

空间复杂度： 需要借用一个hash表，其大小为n，n为nums的长度，所以空间复杂度为O(n)。

5. Redo.25/1/17

暴力算法依旧是一眼

优化的思路错误了

• 以为要用到双指针，但是发现没法实现，始终要对数组进行一次遍历。

• 因为存在首尾元素相加，也存在前两个连续元素相加等等情况，双指针没办法进行高效更新。

看题解才想起来是哈希表

• 哈希表一开始想到的是实时更新，也能通过。

• 题解用的是先预设哈希表，至少复杂度不会增加。

• • 当然上面两种方法在之前都有用过，单循环和两次循环都有，这里也重复贴出来了。（暴力就不贴了）

• 哈希表的成员方法有点忘记了：u_map.find() != u_map.end()

5.1. 实时更新哈希表

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

5.2. 预设哈希表

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