目 录CONTENT

文章目录

数组的应用-两数之和!梦开始的地方!

Hello!你好!我是村望~!
2022-08-11 / 0 评论 / 0 点赞 / 355 阅读 / 694 字
温馨提示:
我不想探寻任何东西的意义,我只享受当下思考的快乐~

两数求和问题

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例: 给定 nums=[2,7,11,15],target=9nums = [2, 7, 11, 15], target = 9
因为 nums[0]+nums[1]=2+7=9nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0,1][0, 1]

一个“淳朴,暴力”的解法:

两层循环来遍历同一个数组;第一层循环遍历的值记为 a,第二层循环时遍历的值记为 b;若 a+b = 目标值,那么 a 和 b 对应的数组下标就是我们想要的答案。

var twoSum = function(nums, target) {
 for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums.length; j++) {
            if (nums[i] + nums[j] === target && i !== j) {
                return [i, j]
            }
        }
    }
    return []
};

image-1660228218378
上面的解法是2层循环!每一层都是n,那么时间复杂度就是nnn*n = O(n2)O(n^2),空间复杂度则只占用了2个(i,j)固定内存!不会随着代码的进行而产生变化!空间复杂度为O(2)O(2)!这是一个典型时间换空间的解法,但是在大部分正常情况下,我们认为运算的时间是比空间更加重要的!

空间换时间,Map 来帮忙

拿我们这道题来说,其实二层遍历是完全不必要的。

大家记住一个结论:几乎所有的求和问题,都可以转化为求差问题。 这道题就是一个典型的例子,通过把求和问题转化为求差问题,事情会变得更加简单。

我们可以在遍历数组的过程中,增加一个 Map 来记录已经遍历过的数字及其对应的索引值。然后每遍历到一个新数字的时候,都回到 Map 里去查询 targetNum 与该数的差值是否已经在前面的数字中出现过了。若出现过,那么答案已然显现,我们就不必再往下走了。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    let map = new Map();
    for (let i = 0; i < nums.length; i++) {
        map.set(nums[i], i)
    }
    for (let i = 0; i < nums.length; i++) {
        let has = map.has(target-nums[i])
        let getMapI = map.get(target-nums[i])
        if(has&&getMapI!==i){
            return [i,map.get(target-nums[i])]
        }
    }
    return []
};

image-1660229704440 可以看到这种速度的确快了很多!

0

评论区