已被阅读 788 次 | 文章分类:日常随笔 | 2022-04-09 01:01
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用
1 示例
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
1 暴力解法
思路:两层遍历;即先用第一个元素跟后面每一个相加,然后用第二个元素跟后面每一个相加,一直到最后一个元素;期间只要有一个相加结果为target,则直接返回;因为假设只对应一种答案
代码如下:
function getIndexArr(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
}
let nums=[2,3,7,5];
let target=9;
getIndexArr(nums,target) // [0, 2]
上面方式简单粗暴;时间复杂度O(n2);下面用动态规划的方式降低时间复杂度
2 动态规划解法
动态规划的基本思路是用空间换时间;核心思想是记录下每步的状态来降低时间复杂度;这个问题的解决思路是
第一 用Map保存每步的值
第二 找到状态表达式,很明显m+n=target;
代码如下:
function getIndexArr(nums,target){
// 定义哈希map
let map=new Map()
// 定义结果数组
let result=[]
for(let i=0;i<nums.length;i++){
// 如果哈希map中没有则存入当前值
if(!map.has(target-nums[i])){
map.set(nums[i],i)
}else{
// 如果有返回结果
result=[map.get(target-nums[i]),i]
}
}
return result
}
let nums=[2,3,7,5];
let target=9;
getIndexArr(nums,target) // [0, 2]
QQ:3410192267 | 技术支持 微信:popstarqqsmall
Copyright ©2017 xiaobaigis.com . 版权所有 鲁ICP备17027716号