原题链接
题目原文：
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].
中文翻译：
给定一个整数数组，返回（两个数字加起来的和等于给定的目标数字）的位置（即数组下标）
你可以假定每个输入例子正好只有一个解，并且你不能够使用同一个元素两次。
这是leetcode的第一题，属于给新手练习用的基础题。无论从什么角度来说，这个题目只要是会写代码的同学，没有谁是想不到解法的。
但是新手往往会陷入一个问题，但凡解题都会选择使用暴力破解办法（brute force）,这样空间复杂度往往会特别大，也是实际应用和面试的大忌，当然，只有在万不得已的情况下才可以考虑暴力破解。
暴力破解法: O(n ^ 2) time
vector<int> twoSum(vector<int>& nums, int target) {
for (int i = 0; i < nums.size(); i++) {
for (int k = 0; k < nums.size(); k++) {
if (i != k) {
if (nums[i] + nums[k] == target)
return {i, k};
}
}
}
return {-1, -1};
}
优化版暴力破解：O(n*logn) time
vector<int> twoSum(vector<int>& nums, int target) {
for (int i = 0; i < nums.size(); i++) {
for (int k = i + 1; k < nums.size(); k++) {
if (nums[i] + nums[k] == target)
return {i, k};
}
}
return {-1, -1};
}
一次遍历解法：O(n) time O(n)space
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> rec;
for (int i = 0; i < nums.size(); i++) {
if (rec.find(target - nums[i]) != rec.end())
return {rec[target - nums[i]], i};
rec[nums[i]] = i;
}
return {-1, -1}
}
网友评论