Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Two Sum

Leetcode algorithms 第 1 题: Two Sum。

题目

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

解答

可以把元数组排序,然后用两个指针分别从头尾向中间扫描,寻找满足要求的一对。但题目要返回的是下标,可以新开一个数组来表示下标,然后对下标进行排序,这样是O(n)的空间复杂度,O(nlogn)的时间复杂度。

对于每个数x,只需要知道target-x是否在数组中。关于查找,可以普通的O(n)查找,也可以O(nlogn)二分查找,但最快的还是哈希表O(1)查找,于是以下使用哈希进行实现,具体的哈希是使用C++的哈希map进行,即unordered_map。一般的map使用红黑树,查找时复杂度仍然为O(logn),不如使用哈希实现的map。

注意,由于x和target-x可能相同,这里采用的是逐个寻找再逐个插入的方法,所以当遍历到答案的后一个数时才找到答案。

代码如下:

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        vector<int> ans;
        unordered_map<int, int> mp; //哈希表
        for (int i = 0; i < numbers.size(); i++)
        {
            auto p = mp.find(target - numbers[i]);
            if (p != mp.end())
            {
                ans.push_back(p->second + 1); //注意是p先
                ans.push_back(i + 1);
                return ans;
            }
            mp.insert(pair<int,int>(numbers[i], i));
        }
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论