interviewalgo
, , ,
Source
Edit
History

1. 两数之和

Introduction

Question：1. 两数之和

解法一

Analysis

解法一：用两个循环来暴力查找，O(n^2)

解法二：一般这种数组的问题，通常可以先排序来把复杂度降低到 O(nlogn)
对于这道题来说，如果数组是有序的，在原来的解法一种的第二层循环就可以用二分查找来优化了，这样时间复杂度就是 O(nlogn) 了。

但是非常尴尬的是，题目要求返回下标，虽然解法二也能做，但是写起来就有点繁琐了。

首先创建一个index数组，按 nums 中的元素只对 index 进行排序
查找时用同样的方法查找，或者用 pair 来做，但是好像区别也不大。由于 Cache 的原因，可能 pair 快一点，但是空间消耗也增加了一倍。下面是用pair实现的版本：

Implement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> twoSum(vector<int>& nums, int target) {
    vector<pair<int, int>> vec;
    for(int i = 0;i < nums.size(); i++)
        vec.push_back(make_pair(nums[i], i));

    auto cmp = [](auto &p1, auto &p2) {
        return p1.first < p2.first;
    };
    sort(vec.begin(), vec.end(), cmp);
    auto tp = make_pair(target, -1);
    for(auto beg = vec.begin(); beg != vec.end(); beg++) {
        tp.first = target - beg->first;
        auto it = lower_bound(beg + 1, vec.end(), tp, cmp);
        if (it != vec.end() && it->first == tp.first) {
            return {beg->second, it->second};
        }
    }
    return {};
}

解法二

Analysis

由于传入数组的大小最多才到 10^3，所以我们可以用时间换空间，利用使用HastMap来解这道题。具体的操作如下：

遍历整个数组，一边遍历一边将数组元素作为 key ，下标作为 value 插入到 HashMap 中，当遍历到第 i 个元素时，我们用 HashMap 快速的判断已经遍历过的元素中是否存在 target - nums[i]。

  • 时间复杂度为O(n)
  • 空间复杂度为O(n)

Implement

1
2
3
4
5
6
7
8
9
10
11
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> imap;
    for (int i = 0;i < nums.size(); i++) {
        auto it = imap.find(target - nums[i]);
        if (it != imap.end()) {
            return {i, it->second};
        }
        imap[nums[i]] = i;
    }
    return {};
}

One More Thing