起源:力扣(LeetCode)
给定一个整数数组 nums 和一个整数目标值 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 <= 103
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- 只会存在一个无效答案
形式一:暴力迭代
暴力迭代就是两层遍历,循环迭代每两个数都进行匹配
JavaScript
var twoSum = function(nums, target) {for (let i = 0; i < nums.length - 1; i++) {for (let j = i+1; j < nums.length; j++) {if (nums[i] + nums[j] === target) {return [i, j]
}
}
}
return [];};
- 工夫复杂度:O($n*n$)
- 空间复杂度:O(1)
python
版本
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if (nums[i] + nums[j] == target):
return [i, j]
return [];
形式二:哈希表
就是用一个对象来存储元素和其索引
- 每一次用目标值
target
– 以后元素,判断其值是否在哈希表中 - 若存在,即返回哈希表中对应的值和以后元素的索引
- 否则,将以后元素机器索引存储到哈希表中
这样就只须要一次遍历,毛病就是须要额定保护一个哈希表
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {let obj = {};
for (let i = 0; i <nums.length; i++) {if (parseInt(target - nums[i]) in obj) {return [obj[target - nums[i]], i];
}
obj[nums[i]] = i;
}
return [];};
- 工夫复杂度:
O(n)
- 空间复杂度:
O(n)
python
class Solution(object):
def twoSum(self, nums, target):
hashtable = dict()
for key, value in enumerate(nums):
if target-value in hashtable:
return [hashtable[target - value], key]
hashtable[value] = key
return []