两数之和等于目标值-蒲公英云

两数之和等于目标值

亦凉 2022-05-27 09:10 277阅读 0赞

题目：

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数，将这两个数通过另一个数组返回。可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]

第一种方法：

使用两层for循环，如果两个数之和等于目标值，返回两个索引，这样可以把每一个数据都遍历到，但是时间复杂度为O(N^2)比较高。
代码实现：

void TwoSum(vector<int>& v1, vector<int>& v2, int key)
{
    for (int i = 0; i < v1.size(); i++)
    {
        for (int j = 0; j < v1.size(); j++)
        {
            if (v1[i] + v1[j] == key)
            {
                v2.push_back(i);
                v2.push_back(j);
                return;
            }
        }
    }
}

第二种方法：

这种方法针对于有序的数组，如果数组重元素不是升序的，需要先将他排序。
第二种方法，我们是这样的，我们先创建两个索引begin和end，分别指向数组中最小的元素和最大的元素，将这两个数加起来，如果之和等于key，俺么直接返回这两个数据的索引；如果两数之和小于key，那么begin++；如果两数之和大于key，那么end–；这样循环，直至begin和end相遇。
代码实现：

void TwoSum(vector<int>& v1, vector<int>& v2, int key)//这个必须是升序的
{
    int begin = 0;
    int end = v1.size() - 1;
    while (begin < end)
    {
        if (v1[begin] + v1[end] == key)
        {
            v2.push_back(begin);
            v2.push_back(end);
            return;
        }
        else if (v1[begin] + v1[end] < key)
            begin++;
        else
            end--;
    }
}

第三种方法：

我们先创建一个unordered_map，假设题目给的数组是v1，我们用key减去v1[0]，如果得到的结果在map中，那说明我们找到了题目要求的两个数，如果得到的结果不在map中，我们把v1[0]和它的索引一起插入map中。循环下去，就可以得到结果了。
因为在哈希中查找的效率是O（1）是非常高的，这样我们就可以以较高的效率完成这道题了。
代码实现：

void TwoSum(vector<int>& v1, vector<int>& v2, int key)
{   //哈希， 下标i作为value传入
    unordered_map<int, int> m;
    for (int i = 0; i < v1.size(); i++)
    {
        unordered_map<int, int>::iterator it = m.find(key - v1[i]);
                                        //没找到返回end()，找到了返回数据对应的迭代器
        if (it != m.end())//找到了
        {
            v2.push_back(m[key - v1[i]]);
            v2.push_back(i);    
        }
        else//没找到插入
            m.insert({ v1[i], i });
    }
}