Posts

例题1 167.两数之和 题面 给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。 你所设计的解决方案必须只使用常量级的额外空间。 示例 1： 输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。 思路 利用数组的有序性，初始化左右两个指针，指向第一个数和最后一个数，如果两个指针所指之数的和大于target，左移右指针，反之右移左指针。（两指针所指之数的和大于target时，如果右指针不变，右移左指针，则两数之和只会变大，永远无法等于target） 为什么这样做不会有遗漏？ 我们可以把这看作是对于暴力的优化。正常来说，我们使用两个循环来遍历所有组合。而这种情况下，我们可以视为，先用左指针从小到大遍历数组，当左指针指向某个数时，我们来关注右指针，右指针从大到小遍历，如果两数之和大于target，那说明当前的右指针所指之数太大，左移，直到两数之和等于target。接下来继续遍历左指针，我们右移左指针，这个时候可以注意到，左指针右移导致左指针所指之数变大，思考一下，那我们还需要从最大值开始遍历右指针吗？当然不需要了，我们完全可以从右指针正指着的位置开始遍历。 于是，左指针不会回头，右指针不会回头，直到两者相遇，那么时间复杂度我们就优化到了O(n). 例题2 三数之和 思路 ...

二分查找 我们仍然从一个最基本的例题开始，随后讲解一下二分的扩展题型。 例题 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1： 输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4] 示例 2： 输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1] 示例 3： 输入：nums = [], target = 0 输出：[-1,-1] 思路 二分查找的基本思路有不少变种，我学习的是红蓝染色法，个人觉得这种方法是非常直观好理解的， 我最开始看的是b站灵茶山艾符的视频。 过去我们了解的二分查找的基本思想可能是从一个有序数组中不断取中值与target比较，相同则返回，不同则分类讨论。而在这里，我们把上述逻辑简化成了如果大于等于target，和小于target两种情况，于是我们分类讨论这两种情况，最终返回第一个大于等于target的数。 先简单说一下思路，左指针left指向最左边，右指针right指向最右边，如果中值小于target，说明需要左移left，反之亦然，下面是代码： 首先这里是闭区间 fun lower_bound(nums: IntArray, target: Int): Int{ // 我们最终返回第一个大于等于target的数 var left = 0 var right = nums.size - 1 // 显然，如果是闭区间的话，左右一开始指向的都是需要遍历（检查）的数 while (left <= right) { // 我们思考一下，left和right处于什么状态时，说明所有数都已经被遍历，由于是闭区间，left > right 时，已完全遍历，while里反着写 val mid = left + (right - left) / 2 if (nums[mid] < target) { left = mid + 1 // 由于是闭区间，这里实际的范围是[left, ... , right] // 关于为什么这里要+1，如果 left = mid ，则数组实际上是[mid, ... , right]，而mid已经是小于target了，target如果存在于这个数组，则一定在[mid + 1, ... , right]中 } else { right = mid - 1 } } return left } 开区间 ...