分享｜2021秋招算法总结7-双指针篇

1. 两数之和：经典简单题，解法很多，常见的是暴力和HashMap，但是也可以用双指针思路。建议面试者用双指针思路做完，自行分析下时间和空间复杂度。
167. 两数之和 II - 输入有序数组：与上一题的区别是这题的输入是已按照升序排列的有序数组。
剑指 Offer 57. 和为s的两个数字：与上一题的区别是，这题的返回值是这个数本身，而非下标。
面试题 16.24. 数对和：与前面题目的区别是要输出数组中两数之和为指定值的所有整数对。
653. 两数之和 IV - 输入 BST：给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
15. 三数之和：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
16. 最接近的三数之和: 给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
18. 四数之和：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
面试题 16.06. 最小差：给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差。
提升1：给一组整数，问能找出多少对整数，使这两个数的和大于/等于/小于一个给定的目标值。
提升2：给一组整数，找到数组中有多少组不同的元素对有相同的和，且和等于目标值，返回对数/所有元素对的集合。
提升3：给一组按绝对值升序排列的数组（有正有负有0），找到两个数使其相加以后等于目标值，返回这两个数的下标/这两个数本身。
提升4：给一组按照升序排列的有序数组，找到两个数的差等于目标值，返回这两个数的下标/这两个数本身。
提升5：给一组整数，从中找到这两个数字使他们的和最接近目标值，返回两数和目标值的差的绝对值。
提升6：给定一个递增的整数数组和一个表示限制的整数，使该子数组中的任意两个元素之间的绝对差小于或者等于这个限制整数，返回满足条件的三元子数组的个数/满足条件的三元子数组的集合。

柱状图装水

注明：此类题目解法较多，双指针只是其中一种解法。

11. 盛最多水的容器：给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
42. 接雨水和面试题 17.21. 直方图的水量：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。这两题虽然题目叙述不太一样，但是代码是一样的。
PS ：接雨水虽然是困难题，但是笔试乃至面试时出现的频率不低，建议大家都有掌握其中一种解法（双指针、动态规划或者单调栈），并熟知这种解法的时间和空间复杂度。接雨水还有个3d接雨水407. 接雨水 II，此题较难，大家量力而行即可，面试遇到的概率不太大。

排序

注明：当题目中指定原地修改、额外常数空间之类的字眼时，可以尝试用双指针思想。当题目输出和索引（下标）有关时，可以尝试用双指针思想。

31. 下一个排列：实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。必须原地修改，只允许使用额外常数空间。
面试题 16.16. 部分排序：给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。
26. 删除排序数组中的重复项：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。
88. 合并两个有序数组：给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

找值

162. 寻找峰值：峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
剑指 Offer 59 - I. 滑动窗口的最大值：给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

调整位置

283. 移动零：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

结束语

刷题刷的是思想，和别人比刷题数目是没有用的。像我虽然刷了666题，但是里面很多都是同题不同叙述，用同一个代码都能跑过去的双胞胎乃至三胞胎题。与其600题刷一遍，不如200题刷3遍或者100题刷N遍，掌握题目的多种解法，多思考算法思路的区别和优缺点。对不同的人来说，刷多少题才能找到工作是个没有固定解答的开放问题，找适合自己的道路就行了。比如以上题目，也许你点开发现你做过了，但是你有都用双指针做过么？你有想过双指针解法和其他解法的区别和优缺点么？如果题目变一变，你又会怎么解决？