1. Two Sum

发表于 | 分类于 | |

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4
5
6
> > Given nums = [2, 7, 11, 15], target = 9,
> >
> > Because nums[0] + nums[1] = 2 + 7 = 9,
> > return [0, 1].
> >	
>

题意是给出一个数组和一个目标数，而且在数组中一定存在两个数加起来之和等于目标数。让你求出数组中加起来等于目标数的两个数的索引。

我想到的就是O（N^2）的算法，有点类似于冒泡排序，两层循环遍历，判断是否a[i]+a[j] == target，如果成立的话就把索引i,j返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//
// Created by chaopengz on 2017/9/12.
//
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int> &nums, int target) {
        vector<int> res;
        for (int i = 0; i < nums.size() - 1; ++i) {
            for (int j = i + 1; j < nums.size(); ++j) {
                if (nums[i] + nums[j] == target)
                {
                    res.push_back(i);
                    res.push_back(j);
                }
            }
        }
        return res;
    }
};

上面的做法虽然可以ac,但是由于是O（n^2）的做法，时间效率较低。其实利用c++的map的索引查找可以达到更快的做法O（nlog(n)）。

首先依旧是对数组进行遍历，取出一个数a[i]后，剩下则是在map中寻找target-a[i]这个数所对应的索引，最后返回即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        vector<int> res;
        map<int, int> numToIndex;
        int findNum;
        for (int i = 0; i < nums.size(); ++i) {
            findNum = target - nums[i];
            if (numToIndex.find(findNum) != numToIndex.end()) {
                res.push_back(numToIndex[findNum]) ;
                res.push_back(i);
            }
            numToIndex[nums[i]] = i;
        }
        return res;
    }
};