数组初相遇–小册专项练习笔记

这是我参与更文挑战的第2天，活动详情查看： 更文挑战

数组经典类型解析

Map的妙用

我们来看一题很常见的求和数组问题： 给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

像上面这道题目，我们在做算法的时候经常碰到，那么我们平常会用什么方法去解呢？

• 暴力解法

也就是我们能想到的最直接的算法，是什么呢？没错，他就是”双循环”(哭出声，没学前脑子里真的只有循环再循环)，让我们用代码来实现一下这个函数：

function getTarget(nums, target) {
    // 空数组就返回
    if(!nums) {
        return
    }
    // 对数组进行两次遍历
    for(let i=0; i < nums.length; i++) {
        for(let j=0; j< nums.length;j++) {
            // 首先要排除同一个元素两次相加，再者两个数相加为目标值
            if(i !== j && nums[i] + nums[j] === target) {
                // 返回一个数组，分别是第一个元素，第二个元素，第一个下标， 第二个下标
                let arr = [nums[i],nums[j],i,j]
                console.log(arr);
                return arr
            }
        }
    }
}

getTarget([2,3,2,11], 4)

// [2, 2, 0, 2]
复制代码

上面的例子可能有没考虑全部的情况，就是展示一下这个思路，这种解法的优点在于，不用考虑很多，就是一个一个算过去，但是这也造成了时间复杂度的提升，经过上一篇算法的数据结构基础的学习，我们都知道，暴力解法的时间复杂度是为O(n^2)的，那随着n的变化，很可能造成超时，那有没有办法解决这个问题呢？那么我们考虑，是不是可以通过空间复杂度来降低时间复杂度呢？答案自然是可以的，那么下面我们就来介绍这种思路。

• Map求和

这里的Map实际是一个对象，这个对象存储了对应元素和下标，也就是将数组中的元素变成了对象，key是数组元素的值，value是数组元素的下标，那么到底怎么使用呢？还是使用上面的例子：

首先我们定义一个空对象Map，当我们查找一个元素时，假如target-nums[i]不能够在对象的key中找到，那么就将{nums[i]:i}存入对象中，如果能找到，那么我们就可以返回所需要的数和下标了，看下面这张图?：

因此，我们可以用代码将上面的思路实现出来：

function getTarget(nums, target) {
    // 空数组就返回
    if(!nums) {
        return
    }
    let Map = {}
    // 对数组进行遍历
    for(let i=0; i < nums.length; i++) {
        // 假如在Map中能找到对应的值，就返回对应的结果
        if( Map[target-nums[i]] !== undefined ) {
            console.log([target-nums[i], nums[i],Map[target-nums[i]], i]);
            return [nums[target-nums[i]], nums[i],Map[target-nums[i]], i]
        }
        // 如果不能，就将这个值存入Map
        Map[nums[i]] = i
    }
}

getTarget([2,3,2,11], 4)

// [2, 2, 0, 2]
复制代码

其实，另外使用ES6中的Map也可以解决，思路是一样的，这里贴一下Map的定义，方便大家理解

Map 对象保存键值对，并且能够记住键的原始插入顺序。任何值(对象或者原始值) 都可以作为一个键或一个值
复制代码

我把自己的思路放在这里跟大家探讨一下：

//  其实就是把Map变成了Map的实例化对象，别的都没什么差别
function getTarget(nums, target) {
    // 空数组就返回
    if(!nums) {
        return
    }
   const map = new Map()
   for(let i =0; i < nums.length; i++) {
       if(map.get(target - nums[i]) !== undefined) {
           console.log([target-nums[i], nums[i],Map[target-nums[i]], i]);
            return [nums[target-nums[i]], nums[i],Map[target-nums[i]], i]
        }
        
       map.set(nums[i], i)
   }
}

getTarget([2,3,2,11,2,45,2,2,2], 4)
// [2, 2, 0, 2]
复制代码

大家有更好的思路欢迎交流

用了都说好的双指针

双指针解法不多说了吧，基本人人好评，在数组中运用得当，不光能解题，还能提高效率，下面我们就来在题目中用双指针来解题吧！

我们来看一题合并并排序数组问题： 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。。

• 传统解法

传统解法是很多人第一次做这个题目时，轻易想到的，不就是把两个数组合并，并且排个序，这又啥难的？看代码：

function mergeTwoArr(nums1, nums2) {
    nums1 = [...nums1, ...nums2]
    nums1.sort();
    return nums1
}

let nums1 = [1,4,7], nums2 = [2,3,9]
let arr = mergeTwoArr(nums1, nums2)
console.log(arr);
复制代码

之前看评论有看到过，”排序这个事情前端来做也太简单了吧！”，哈哈，没错，有对应的方法就是好啊，不过sort的本质，实际上是对整个数组进行遍历，一个个比较大小，这样实际上是很长的一个过程，如果数组很大，会造成性能上的占用，MDN上也有这样的描述：由于它取决于具体实现，因此无法保证排序的时间和空间复杂性。

• 双指针解法

先来说一下什么是双指针，顾名思义，他有两个指针，分别指向，我们通过一张图来体会一下，就能明白了?：

因为题目是需要把nums2并入nums1，并且两者都是有序数组，因此我们可以考虑把指针指向两者的尾部，具体的思路看下图：

看懂了图，我们接下来用代码来实现一下这个双指针：

function mergeTwoArr(nums1,m, nums2,n) {
    // 定义两个指针分别指向原数组尾部，一个变量用于指向合并后的尾部
    let needle1 = m-1, needle2 = n-1, allNum = m+n-1

    while(needle1 >= 0 && needle2 >= 0) {
        if(nums1[needle1] >= nums2[needle2]) {
            // 将两者的更大的那个元素放入尾部
            nums1[allNum] = nums1[needle1]
            // needle1往前移一位
            needle1--
            // 最后的位置往前移一位
            allNum--
        }else {
            // 将两者的更大的那个元素放入尾部
            nums1[allNum] = nums2[needle2]
            // needle1往前移一位
            needle2--
            // 最后的位置往前移一位
            allNum--
        }
    }

    // 如果nums2有的元素比nums1的最小的元素更小，且总元素更多，那么此时会剩下几个元素
    while(needle2 >= 0) {
        // 将nums2剩下的元素都放入nums1的前面
        nums1[allNum] = nums2[needle2]
        allNum--
        needle2--
    }
}

let nums1 = [3,4,7], nums2 = [2,3,9,11,15]
mergeTwoArr(nums1,3, nums2,5)
console.log(nums1, nums2);

// [2, 3, 3, 4, 7, 9, 11, 15]
// [2, 3, 9, 11, 15]
复制代码

我们再来看一题升级的两数求和的问题–三数求和：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

针对这题我们用传统方法的话就是用三次遍历，但是这样直接把时间复杂度弄到了O(n^3)的程度，那就很耗费性能了，而此时我们应该考虑用刚才学到的指针来解这道题目：

• 解题思路

其实三数求和，我们可以将其认定为固定一个数，然后另外两个数与这个固定的数的和为0即可，另外两个数通过指针来指定，可以从固定数的后一个数和整个数组的最后一个数两个位置出发，如果三数相加的结果大于0，证明需要将最后一个指针往前挪一位，如果小于0，需要将前面的指针往后移一位，看到这里大家也一定发现了，没错，第一步重要工作是对数组进行从小到大的排序，为了帮助大家理解，我画了下面的图?：

各部门注意了，这里强调一个点，接下来我们需要往中间挪动指针，为了避免出现重复数组，左右侧指针每次挪动一位，我们都要和前一位判断是否相等，如果相等则下一位，如果不相等再重复上述过程，直到1号和2号指针指向了同一个数，那么固定数的这一轮循环才算走完，接下来固定第二个数，同样要判断是否相等，直到出现不相等的数才固定，接下来重复上述整个过程。接下来我们看一下编码实现过程：

function getThreeSum(nums) {
    // 定义一个空数组用来存放最终结果
    let arr = []
    // 对数组进行排序
    nums = nums.sort((a, b) => {
        return a-b
    });

    const arrLength = nums.length

    // 对数组进行遍历,遍历到倒数第三个数就行，后面两个正好指针
    for(let i = 0; i < arrLength-2; i ++) {
        // 定义左右指针
        let left = i + 1, right = arrLength - 1
        // 每次循环先判断当前数与前一个数是否相等，相等就下一个循环
        if(i > 0 && nums[i] === nums[i-1]) {
            continue
        }
        while(left < right) {
            // 如果和小于0
            if(nums[i] + nums[left] + nums[right] < 0) {
                // 左指针右移一位
                left++
                // 并且判断下一位与当前位是否相等
                while(left<right&& nums[left] === nums[left-1] ) {
                    left++
                }
            }else if(nums[i] + nums[left] + nums[right] > 0) {
                // 右指针左移一位
                right--
                // 并且判断前一位与当前位是否相等
                while(left<right&& nums[right] === nums[right+1] ) {
                    right--
                }
            }else {
                // 把这一组结果放到数组中
                arr.push([nums[i], nums[left], nums[right]])

                // 接下来就是确定下一组数据了
                left++
                right--
                // 并且判断下一位与当前位是否相等
                while(left<right&& nums[left] === nums[left-1] ) {
                    left++
                }
                // 并且判断前一位与当前位是否相等
                while(left<right&& nums[right] === nums[right+1] ) {
                    right--
                }
            }
        }
    }

    // 返回最终结果
    console.log(arr);
    return arr
}

getThreeSum([1, 5, 7, 3,-5, -4, -10, 9, 11, -4, 0])
// [[-10, 1, 9],[-10, 3, 7],[-5, -4, 9],[-5, 0, 5],[-4, 1, 3]]
复制代码

那么，这种两边向中间移动的其实是一种特殊的双指针，我们称为对撞指针，你学废了吗(^_^*)

总结

关于数组的一些经典典型的解题思路，就是上面这些了，一定一定要自己看了然后解题，不要直接看代码，才能促进自己对思路的理解哦。