LeetCode题解 C++ Two Sum

最近要开始准备实习了,为了让自己显得不那么弱,所以拾起了以前的A题的感觉,开始在大名鼎鼎的LeetCode上开始刷题,废话不多说了,就从第一题开始吧。

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:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

说实话重新开始做算法题已经手生了,刚开始做没有想很多,就开始暴力的用O(n^2)的方法,果然不出所料超时了. 原来思路是,对原来的数组做一个排序,然后两边的数往中间夹逼.代码如下

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> numbers = nums; std::sort(numbers.begin(), numbers.end()); int length = numbers.size(); int left = 0; int right = length - 1; int sum = 0; vector<int> index; while(left < right) { sum = numbers[left] + numbers[right]; if(sum == target) { for(int i = 0; i < length; ++ i) { if(nums[i] == numbers[left]) { index.push_back(i + 1); } else if(nums[i] == numbers[right]) { index.push_back(i + 1); } if(index.size() == 2) break; } } else if(sum > target) { right --; } else { left ++; } } return index; } };

思考了一会才想到,原来的hash方法其实可以把时间缩短到O(n). 具体思路是我把原来的数组用map记录下来,每次记录时比较值和target的差值,如果在map中可以找到,就实现匹配,缩短时间.

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { map<int, int> m; vector<int> index; for(int i = 0; i < nums.size(); ++ i) { if(m.count(target - nums[i]) != 0) { index.push_back(m[target - nums[i]]); index.push_back(i); break; } m[nums[i]] = i; } return index; } };

加油继续A题……/(ㄒoㄒ)/~~