优秀的商城网站首页设计,网站素材设计框架,如何做公司网站制作,网页大图素材两数之和II_二分法||二分查找
1 题目描述
https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/
给你一个下标从 1 开始的整数数组 numbers #xff0c;该数组已按 非递减顺序排列 #xff0c;请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设…两数之和II_二分法||二分查找
1 题目描述
https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/
给你一个下标从 1 开始的整数数组 numbers 该数组已按 非递减顺序排列 请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] 则 1 index1 index2 numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
2 思路
看到这一个题目数组和有序第一个想法就是二分查找当然看了官方题解之后发现还有双指针做法。
做法很简单给定了target我们对数组numbers进行遍历对于numbers的每一个元素重新在数组中寻找和该元素之和为target的元素。如果找到的元素和遍历到的元素重复了那么继续遍历然后再寻找如果不重复那就将两个元素的位置都加一获得真实位置然后返回。
public int[] twoSum(int[] numbers, int target) {int pre 0;for (int i 0; i numbers.length; i) {if (i 0 numbers[i] pre) // 如果遇到重复元素就别浪费这个时间了。continue;int other_tar target - numbers[i];int pos biSearch(numbers, other_tar);if (pos 0) {if (pos i) continue; // 防止找到自己头上, 比如参数是([0,4,5], 8), 就有会找到两个4。return new int[]{i 1, pos 1}; // 索引1变成真实位置。}pre numbers[i]; // 记录前一个值}return null;
}那么最重要的问题是如何进行二分查找
我们就事论事如何分析这个题目呢
相似题目可以看我的这篇文章【刷题笔记】H指数||数组||二分查找的变体
题目本身已经强调了非递减顺序也就是说数组中可能会存在一些相等的元素。举个例子
towSum([1,3,4,4], 8)当我们遍历到第一个4的时候为了让和为8我们需要在数组中找到另一个为4的元素。如果二分是普通的二分查找 if (numbers[mid_index] num) {return mid_index;}
else if (numbers[mid_index] num) l real_mid 1;
else r real_mid - 1;我们极有可能在碰到第一个4的时候就返回了其坐标而这和我们题目中的要求是冲突的。那么我们就会接着遍历numbers数组碰到第二个4然后继续进行二分查找找到了第一个4返回位置发现这个组合是符合要求的最后我们返回的两个位置是[4,3]。我替你们试过了就算你返回的的两个坐标是对的还是要保证坐标是从小到大的反过来也会报错。
怎么解决这种存在多个相等元素的问题呢我的解决方法是分成两步
遍历numbers的时候遇到重复元素只遍历第一个。上面代码中的 if (i 0 numbers[i] pre) // 如果遇到重复元素就别浪费这个时间了。continue;就是解决这个问题的。
在二分查找的时候只找重复元素的最后一个。这样假设碰到多个重复元素而且恰好两个重复元素之和等于我们target的情况最终返回的坐标一定是递增顺序的。
那么我们接下来考虑怎么在二分查找的时候找到最后一个符合条件的元素呢
对于二分查找有两个最重要的问题如何计算mid如何跳转left和right。
我在【刷题笔记】H指数||数组||二分查找的变体这篇博客中提出了一个思考的范式 这个两个问题本身是一个问题只要我们确定了如何跳转left和right就能确定如何计算mid。 这只是我的一点浅薄的看法大家要根据自己的刷题情况实时更新自己的理念我考虑出来的东西也不一定具有普适性我只是刚刷题的菜鸡。
怎么理解上面这句话呢比如我们这道题我们确定了目标是寻找满足条件即等于other_tar的最后一个元素也就是右边界一个很符合直觉的想法就是left指针是不断右移的要找右边界left指针最合适。 那么我们看到当遇到这种情况的时候numbers[mid]other_tarmid可能是右边界吗可能。那mid右边的位置还可能是右边界吗不一定。如果left移动到mid右边会不会错过右边界可能会。所以为了避免这种跳过边界的可能性当mid满足条件的时候我们不是直接返回mid而是让left转移到mid的位置上通过left不断寻找右边界。而当numbers[mid] other_tar的时候让left当numbers[mid] other_tar的时候right--这些都是常规操作了。
也就是说当查找边界的时候我们的left指针最后可能会指向边界。为什么是可能因为数组里可能没有我们要找的值这时候left一路向右势不可挡直接窜到了数组的边界之外也是可能的。
现在我们解决了第二个问题如何跳转left和right。那么我们回过头解决第一个问题如何计算mid。
第二个问题我们可以直接考虑在只剩下两个元素的时候即只剩下left和right的时候该如何计算mid。 众所周知当我们在只剩下两个元素的时候mid元素要么是(left right) / 2放在left上要么是(left right) / 2 1放在right上。
我们已经确定了left在某些条件下是可能直接跳转到mid上的 如果让midleft下一步如果left需要跳转leftmid然后midleft。。。。。。无限循环。
所以为了避免死循环当只有偶数个元素的时候我们需要让mid跳转到中间两个元素的后一个元素上。所以我说当我们确定了left和right的跳转问题之后如何计算mid的问题就迎刃而解。
当然传统的二分法left跳转到mid1right跳转到mid-1不会出现死循环的。咱们现在讨论的是边界问题所以有些特殊。
我还是那句话我花生豆大的小脑仁接受不了太多弯弯绕绕面对二分问题的时候left和right的取值我倾向于直接使用真实位置即从1开始的位置。
public int biSearch(int[] numbers, int num) {int l 1, r numbers.length;...
}这样有一个好处就是符合我们的思维直觉本身二分法的变化就多能简化思考的地方就简化思考。
那么如果l~r范围内闭区间的元素个数是奇数个(lr)/2就是中间数的真实位置如果是偶数个我们就设为(lr)/2 1。这个方法虽然笨但是符合我们的思维直觉。 public int biSearch(int[] numbers, int num) {int l 1, r numbers.length;while (l r) { // 一旦两个指针重合遍历结束要么是找到了要么是l跳到边界外了。int real_mid (l r) / 2 ((l - r 1) % 2 0 ? 1 : 0);int mid_index real_mid - 1;if (numbers[mid_index] num) l real_mid;else if (numbers[mid_index] num) l real_mid 1;else r real_mid - 1;}if (l numbers.length numbers[l-1] num) return l-1;else return -1;
}在这里所有的指针我都使用了真实值只有在用到numbers[mid_index]的时候才用的索引。当然这些都是我自己的习惯。
因为我们是用left指针来判断边界left在跳转的过程中我们计算mid的时候是选择了靠右型如果left跳转到mid1的位置可能跳出边界。
所以我们最后的判断条件是if (l numbers.length numbers[l-1] num) return l-1; 返回索引。
3 代码
class Solution {public int[] twoSum(int[] numbers, int target) {int pre 0;for (int i 0; i numbers.length; i) {if (i 0 numbers[i] pre)continue;int other_tar target - numbers[i];int pos biSearch(numbers, other_tar);if (pos 0) {if (pos i) continue;return new int[]{i 1, pos 1};}pre numbers[i];}return null;}public int biSearch(int[] numbers, int num) {int l 1, r numbers.length;while (l r) {int real_mid (l r) / 2 ((l - r 1) % 2 0 ? 1 : 0);int mid_index real_mid - 1;if (numbers[mid_index] num) l real_mid;else if (numbers[mid_index] num) l real_mid 1;else r real_mid - 1;}if (l numbers.length numbers[l-1] num) return l-1;else return -1;}
}
