手机软件开发网站,wordpress商城版,培训机构seo,深圳全网建站公司推荐目录1、暴力#xff0c;超时2、双指针滑动窗口条件限制 AC3、观看题解#xff08;吸取他人经验#xff09;1、二分查找2、双指针3、双指针二分查找给定一个已按照升序排列 的有序数组#xff0c;找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 …
目录1、暴力超时2、双指针滑动窗口条件限制 AC3、观看题解吸取他人经验1、二分查找2、双指针3、双指针二分查找给定一个已按照升序排列 的有序数组找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2其中 index1 必须小于 index2。
说明:
返回的下标值index1 和 index2不是从零开始的。 你可以假设每个输入只对应唯一的答案而且你不可以重复使用相同的元素。 示例:
输入: numbers [2, 7, 11, 15], target 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 1, index2 2 。
1、暴力超时
class Solution {
public:vectorint twoSum(vectorint numbers, int target) {int n numbers.size();int flag0;vectorint res;for(int i0;in;i){flag0;for(int ji1;jn;j){if(numbers[i]numbers[j]target){res.emplace_back(i1);res.emplace_back(j1);flag1;break;}}if(flag1) break;}return res;}
};2、双指针滑动窗口条件限制 AC
在做题提交的过程中发现了几处不容易想到的地方 1、numbers中的元素是递增的但是这个递增不是numbers[i]numbers[i],而是numbers[i]numbers[i1] 2、numbers中的元素有正有负可能连续好几个都是0 3、一开始我想首先找到小于等于target的元素个数这样的话两个值只需要在这些元素中找就可以了但是事实并非如此。 例如target0numbers[] {-3,3,.....},如果用numbers[i]target显然只能到第一个元素所以我又添加了一个限制条件 (i1 numbers[i-1]numbers[i]0)(因为观察的是两个元素相加的结果所以这样肯定是对的) 所以根据思考之后的修改为
for(int i0;in;i)
{if(numbers[i]target || numbers[i]0 ||(i1 numbers[i-1]numbers[i]0)){num_smaller_than_target;}else{break;}
}之后只需要在0~num_smaller_than_target-1的范围内寻找两个数就可以了 然后使用双指针一开始L指向0R指向num_smaller_than_target-1并且保证LR来循环 在循环过程中时时注意sum numbers[L]numbers[R], 1、如果sumtarget,说明我们已经找到值了直接退出 2、如果sumtarget说明左值一定过小右边界由于是从大到小缩减的此时不做改变因为也不确定右边界是大是小 3、如果sumtarget,说明右值一定过大选择减少右值由于左边界是从小到大的此时不做改变因为也不确定左边界是大是小
class Solution {
public:vectorint twoSum(vectorint numbers, int target) {int n numbers.size();int flag0;vectorint res;int num_smaller_than_target0;//首先找到小于等于target的元素个数for(int i0;in;i){if(numbers[i]target || numbers[i]0 ||(i1 numbers[i-1]numbers[i]0)){num_smaller_than_target;}else{break;} }int L0;int Rnum_smaller_than_target-1;//两个指针从两边往中间缩while(LR){int sum numbers[L]numbers[R];if(sumtarget){res.emplace_back(L1);res.emplace_back(R1);break;}//当和小于目标说明左值肯定过小else if(sumtarget){L;}//当和大于目标说明右值肯定过大else {R--;}}return res;}
};因为有要求 所以我们来验证一下重复结果是否输出一致 显然正确。
3、观看题解吸取他人经验
1、二分查找
在数组中找到两个数使得它们的和等于目标值可以首先固定第一个数然后寻找第二个数第二个数等于目标值减去第一个数的差。利用数组的有序性质可以通过二分查找的方法寻找第二个数。为了避免重复寻找在寻找第二个数时只在第一个数的右侧寻找。
class Solution {
public:vectorint twoSum(vectorint numbers, int target) {int n numbers.size();int flag0;for(int i0;in;i){int low i1;int high n-1;while(lowhigh){int mid (high - low) / 2 low;if (numbers[mid] target - numbers[i]) {return {i 1, mid 1};}else if (numbers[mid] target - numbers[i]) {high mid - 1;} else {low mid 1;}}}return {};}
};总结有序序列查找值固定的数可以考虑二分查找优化
2、双指针
这是官方题解和我一开始用的思路是一样的即双指针。
class Solution {
public:vectorint twoSum(vectorint numbers, int target) {int low 0, high numbers.size() - 1;while (low high) {int sum numbers[low] numbers[high];if (sum target) {return {low 1, high 1};} else if (sum target) {low;} else {--high;}}return {-1, -1};}
}; 而我做的一开始排除一些元素的方法好像没有对时间有很多优化。。。
3、双指针二分查找
class Solution {
public:vectorint twoSum(vectorint numbers, int target) {int low 0, high numbers.size() - 1;while (low high) {int middle (lowhigh)*0.5;//1、目标在middle左侧重置highif(numbers[low]numbers[middle]target){high middle-1;}//2、目标在middle右侧,重置lowelse if(numbers[high]numbers[middle]target){low middle1;}//3、重置lowelse if(numbers[low]numbers[high]target){low;}//4、重置highelse if(numbers[low]numbers[high]target){high--;}//5、sum等于targetelse{return {low1,high1}; }}return {0,0};}
};不知道为什么同样的思路用java速度可以达到1ms而c却不行。
