LeetCode 1 Two Sum

Online Judge

问题描述

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

问题分析与思路

  问题描述简单一点说的话，就是在一个数组中，找两个数字相加能得到target，输出这两个数字的index。
思路如下：
  如果是想通过遍历来暴力搜索，复杂度O(n^2)那结果一定会超时，所以这个方法肯定PASS。
  要想节约时间，提高效率，那就需要做一些其他的处理。由于最后需要输出数字的index，所以如果通过排序之后查找则得不到数字的index，因此需要保存数字的index。这个时候就可以想到map的数据结构，map中key和value分别存储数组的元素和元素对应的index，这样在查找是否存在某一元素的时候可以很快的获得这一元素所对应的index，复杂度O(n)。
  另外，这里考虑到这个数组不一定是一个集合，比如说会有重复的元素，比如说numbers={2,2}, target=4，那么在这种情况下map中存储的key多对应的index应该是多少呢？一个key只能对应一个value，所以这里我想的是，当key已经存在时，则删除这个key，重新添加进新的key和value，也就是说，相同的key，map中存储的value是数组中最后一个key所对应的value。因为在问题描述中说可以假设每组输入都可以得到唯一的一个解，所以这样做不会影响结果的正确性。

问题求解

  C++的解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        map<int, int> numsMap;
        for (int i = 0; i < nums.size(); i++)
        {
            if (numsMap.count(nums[i]) == 1)
            {
                numsMap.erase(nums[i]);
            }
            numsMap.insert(pair<int, int>(nums[i], i));
        }
        for (int i = 0; i < nums.size(); i++)
        {
            map<int, int>::iterator it = numsMap.find(target-nums[i]);
            if ( it != numsMap.end() && numsMap[target-nums[i]] > i)
            {
                result.push_back(i+1);
                result.push_back(numsMap[target-nums[i]] + 1);
                break;
            }
        }
        return result;
    }
};

相关知识点总结

关联容器

   两个基本的关联容器类型是map和set，它们的对象所包含的元素都具有不同的键，不允许为同一个键添加第二个元素。如果一个键必须对应多个实例，则需要使用multimap或multiset类型，这两种类型允许许多个元素拥有相同的键。

pair类型

-   pair p1(v1, v2)  创建一份pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，而second成员初始化为v2。

map类型

使用下标访问map对象

   使用下标访问map与使用下标访问数组或vector的行为截然不同：用下标访问不存在的元素将导致在map容器中添加一个新的元素，它的键即为该下标值。

insert操作

-  m.insert(e)  e是一个value_type类型的值。如果键(e.first)不在m中，则插入一个值为e.second的新元素；如果该键在m中已存在，则保持m不变。

查询操作

-  m.count(k)  返回m中k的出现次数。对于map对象，count成员的返回值只能是0或者1，如果返回值非0，则可以使用下标操作符来获取该键所关联的值，而不必担心这样做会在map中插入新的元素。
-  m.find(k)  如果m容器中存在按k索引的元素，则返回指向该元素的迭代器。如果不存在，则返回超出末端迭代器。

删除操作

-  m.erase(k)  删除m中键为k的元素。返回size_tyoe类型的值，表示删除的元素个数

迭代遍历

  map提供begin和end运算。下面是一个迭代遍历的例子：

1
2
3
4
5
6
7
map<string, int>::const_iterator map_it = word_count.begin();

while (map_it != word_count.end()) {
    cout << map_it->first << " occurs "
         << map_it->sencond << " times" << endl;
    ++map_it;
}

  首先，初始化map_it迭代器，使之执行word_count的第一个元素。只要该迭代器不等于end的值，就输出当前元素并给迭代器加1。