题目描述：
标签：数组
难度：简单
描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
- 2 <= nums.length <= 104
- 109 <= nums[i] <= 109
- 109 <= target <= 109
- 只会存在一个有效答案
题解
题目理解
- 考察思路：求和转换为求差
解法一：暴力破解法
解题思路
- 核心思路：target - nums[i] = nums[j]，i !== j && j > i
代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let result = [];
for(let i = 0; i < nums.length; i++) {
const other = target - nums[i];
// i < j
const newArray = nums.slice(i+1);
// 注意 indexOf 的时间复杂度
const index = newArray.indexOf(other);
if (index > -1) {
result = [i, index + i + 1];
}
}
return result;
};
算法分析
- 时间复杂度：O(n^2)
-
空间复杂度：O(1)
image.png
解法二：双层 for 循环(双指针)
解题思路
核心思路：target - nums[i] = nums[j]，i !== j && j > i
image.png
代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let result = [];
for(let i = 0; i < nums.length; i++) {
for(let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
result = [i, j];
}
}
}
return result;
};
算法分析
- 空间复杂度：O(n^2)
-
时间复杂度：O(1)
image.png
解法三：Map结构实现时间换空间
解题思路
- 核心思路：target - nums[i] = nums[j]，i !== j && j > i
- Map{nums[i], i}
代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let result = [];
let map = new Map();
for(let i = 0; i < nums.length; i++) {
const other = target - nums[i];
if (map.has(other)) {
result = [i, map.get(other)];
} else {
map.set(nums[i], i);
}
}
return result;
};
算法分析
- 时间复杂度：O(n)
-
空间复杂度：O(n)
image.png
总结
- 题转化为求差问题。几乎所有的求和问题都可以转化为求差问题。这道题就是一个典型的例子，通过把求和问题转化为求差问题，事情会变得更加简单。
- 遇到双层循环时，考虑能不能用空间换时间，优化为一层循环。
