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].
UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.
这道题一看就知道用暴力搜索肯定没问题，而且猜到OJ肯定不会允许用暴力搜索这么简单的方法，于是去试了一下，果然是Time Limit Exceeded，这个算法的时间复杂度是O(n^2)。那么只能想个O(n)的算法来实现，整个实现步骤为：先遍历一遍数组，建立map数据，然后再遍历一遍，开始查找，找到则记录index。代码如下：
C++ 解法一：
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> m; vector<int> res; for (int i = 0; i < nums.size(); ++i) { m[nums[i]] = i; } for (int i = 0; i < nums.size(); ++i) { int t = target - nums[i]; if (m.count(t) && m[t] != i) { res.push_back(i); res.push_back(m[t]); break; } } return res; } };
Java 解法一：
public class Solution { public int[] twoSum(int[] nums, int target) { HashMap<Integer, Integer> m = new HashMap<Integer, Integer>(); int[] res = new int[2]; for (int i = 0; i < nums.length; ++i) { m.put(nums[i], i); } for (int i = 0; i < nums.length; ++i) { int t = target - nums[i]; if (m.containsKey(t) && m.get(t) != i) { res[0] = i; res[1] = m.get(t); break; } } return res; } }
或者我们可以写的更加简洁一些，把两个for循环合并成一个：
C++ 解法二：
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> m; for (int i = 0; i < nums.size(); ++i) { if (m.count(target - nums[i])) { return {i, m[target - nums[i]]}; } m[nums[i]] = i; } return {}; } };
Java 解法二：
public class Solution { public int[] twoSum(int[] nums, int target) { HashMap<Integer, Integer> m = new HashMap<Integer, Integer>(); int[] res = new int[2]; for (int i = 0; i < nums.length; ++i) { if (m.containsKey(target - nums[i])) { res[0] = i; res[1] = m.get(target - nums[i]); break; } m.put(nums[i], i); } return res; } }
本文转自博客园Grandyang的博客，原文链接：两数之和[LeetCode] Two Sum ，如需转载请自行联系原博主。