LeetCode1.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.

Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

分析

初步想法，默认为vector中每个元素均为正数，使用数组记录每个出现数字的位置，就类似于map，然后提交发现数据中有负数，当时的心情是：好久不刷题，都回退到这地步了吗？ 改用map存储，就解决了。 发现find和distance两个神器，测试了一下，也能解决，查看其STL实现源码，居然是O（n）的！

实现代码

用时：809ms 时间复杂度： O（n2）

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> result; //sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); ++i) { int j = target - nums[i]; vector<int>::iterator it = find(nums.begin(), nums.end(), j); if (it != nums.end() && distance(nums.begin(), it) != i) { result.push_back(i); result.push_back(distance(nums.begin(), it)); break; } } return result; } };

用时：26ms 时间复杂度： O（nlogn）

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> result; map<int, int> mp; for (int i = 0; i < nums.size(); ++i) { mp.insert(pair<int, int>(nums[i], i)); } for (int i =0;i < nums.size(); ++i) { int j = target - nums[i]; map<int, int>::iterator it = mp.find(j); if (it != mp.end() && mp[j] != i) { result.push_back(i); result.push_back(mp[j]); break; } } return result; } };