两数之和等于目标值

亦凉 2022-05-27 09:10 192阅读 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 });
        }
    }

测试程序及运行结果：  
![这里写图片描述][70]

[70]: /images/20220527/30a59eaf847f45d798958fdde2106475.png