JavaScript刷LeetCode拿offer-双指针技巧（下）

一、前言

本篇主要介绍双指针技巧的第二类题型对数组进行预处理之后再采用双指针遍历。

在 Medium 难度的题目中此类问题可以归纳为 K-Sum 问题

• 两数之和【881. 救生艇】

• 三数之和【16. 最接近的三数之和】、【15. 三数之和】、【923. 三数之和的多种可能】

• 四数之和【18. 四数之和】

二、881. 救生艇

第 i 个人的体重为 people[i]每艘船可以承载的最大重量为 limit。每艘船最多可同时载两人但条件是这些人的重量之和最多为 limit。返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

由题意可知保证所需的最小船数意味着每一趟尽可能地搭载两个人并且他们的重量最接近最大重量以便后续趟次能够组成两个人。

解题的关键就在于每趟尽可能地从数组中找出和值小于最大重量的最大值最小值的二元组。

那么对数组排序预处理之后可以很容易地从左侧找到最小值右侧找到最大值双指针再向中间遍历即可解题。

三、16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数使得它们的和与 target 最接近。返回这三个数的和假定每组输入只存在唯一答案。

朴素解法就是通过三层循环枚举各种排列情况来找到最接近的和值时间复杂度为 O(n^3)。

这里可以利用降维思想将其转化为两数之和的问题那么解题思路和【881. 救生艇】如出一辙

时间复杂度被降低为 O(nlogn+n^2)。

四、15. 三数之和

给定一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a + b + c = 0 找出所有满足条件且不重复的三元组。

有了上述题目的铺垫再看本题是不是会浮现以下解题范式

• 降维思想将三数之和转化为两数之和的问题

• 对数组进行排序将双循环问题转化为单循环问题

对于不重复三元数组这一条件同学们第一时间可能会想到采用 HashTable 来去重但是整个双指针解题的过程中三个数始终保持着非递减序列的特性那么遇到重复数字直接跳过即可

参考视频传送门

五、923. 三数之和的多种可能

给定一个整数数组 A以及一个整数 target 作为目标值返回满足 i < j < k 且 A[i] + A[j] + A[k] == target 的元组 i, j, k 的数量。

1、双指针解法

本题的难度在于含有重复数字时双指针无法完整地统计出两数之和的所有排列。

以数组 [2, 2, 6, 6] 为例寻找和值为 8 时无论你怎么设置双指针的移动规则只能得出两组和值为 8 的组合所以对于重复元素就必须得利用排列组合相关的数学知识来处理。

仍然以和值 8 为例会有如下两种情况

• 如果数组的形式为 [2, 2, 6, 6]那么排列组合数就是 2 * 2

• 如果数组的形式为 [4, 4, 4, 4]那么排列组合数就是 4 * 3 / 24个中取2个

那么寻找到满足条件的和值之后还需要将双指针再次向前移动找出相应的个数来计算其组合数

从上述代码中可以发现计算重复数组合的部分非常复杂。

2、数学方法 – 组合

现在同学们可以尝试**逆向思维**枚举所有和值为目标值的三元组那么只要知道三元组中的数字在数组 A 中的数量即可计算出组合数。

相比较数组 A 的长度target 则小很多那么时间复杂度可以大大地降低为 O(n+target^2)另外需要 O(n) 的空间复杂度来存储数组 A 中数字的个数。

六、18. 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target判断 nums 中是否存在四个元素 abc 和 d 使得 a + b + c + d 的值与 target 相等找出所有满足条件且不重复的四元组。

理解【15. 三数之和】的解题思路之后这道题目本质上的区别就是多了一个循环。

写在最后

算法作为计算机的基础学科用 JavaScript 刷一点也不丢人ε=ε=ε=┏(゜ロ゜;)┛。

本系列文章会分别给出一种算法的3种难度的总结篇简单难度中等难度以及困难难度。在简单难度中会介绍该算法的基本知识与实现另外两个难度着重讲解解题的思路。

如果本文对您有所帮助可以点赞或者关注来鼓励博主。