【算法笔记:求元素之和等于目标值的索引】暴力解法和动态规划解法

已被阅读 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号