南宁 网站建设 公司,重庆市园林建设有限公司网站,音乐app界面设计,做婚礼效果图的网站有哪些一、题目
输入一个递增排序的数组和一个数字s#xff0c;在数组中查找两个数#xff0c;使得它们的和正好是s。如果有多对数字的和等于s#xff0c;则输出任意一对即可。
示例 1#xff1a; 输入#xff1a;nums [2,7,11,15], target 9 输出#xff1a;[2,7] 或者 [7…一、题目
输入一个递增排序的数组和一个数字s在数组中查找两个数使得它们的和正好是s。如果有多对数字的和等于s则输出任意一对即可。
示例 1 输入nums [2,7,11,15], target 9 输出[2,7] 或者 [7,2] 示例 2 输入nums [10,26,30,31,47,60], target 40 输出[10,30] 或者 [30,10] 限制
1 nums.length 10^5 1 nums[i] 10^6
二、题目分析解题思路
2.1 从头往后遍历法
有没有人和我一样想着从头往后遍历例如 第一个用例 271115 依次把每个数字 与 target - nums[i] 存到 map 里 存成这样 27 72 … 例如先 存 27 再遍历 7 时 计算 target - 7 2 ,再去用 map.find(2); 找到了即可 否则继续往后遍历
代码实现
class Solution {
public:vectorint twoSum(vectorint nums, int target) {mapint, int mapTemp;for(int i 0; i nums.size(); i){if(nums[i] target){break;}int iTemp target - nums[i];if(mapTemp.find(iTemp) mapTemp.end()){mapTemp.insert(make_pair(nums[i], iTemp));}else{nums.resize(0);auto iter mapTemp.find(iTemp);nums.push_back(iter-first);nums.push_back(iter-second);break;}}return nums;}
};虽然过了但是可以看到所耗时间和所额外开辟的空间都非常大这代码还不如不写 时间复杂度常规遍历 O(N) 加上每一次的 map.find nLog(n) ,还额外开辟了map 存储 2N的空间太鸡肋了完全忽略了 升序这一个特点 因此可以考虑使用双指针法
2.2 双指针遍历法
以示例 1 的用例来看数组是升序左小右大那么只需要做如下操作 代码实现
class Solution {
public:vectorint twoSum(vectorint nums, int target) {int left 0;int right nums.size() -1;while(left right){if((nums[left] nums[right]) target){//说明右边的数字太大了right--;}else if((nums[left] nums[right]) target){//说明左边的数字太小了left;}else{nums[0] nums[left];nums[1] nums[right];nums.resize(2);break;}}return nums;}
};是不是立马好了一点但是感觉还是很慢还有没有优化的空间呢
2.3 缩减范围双指针法
我们继续来看 这一组用例 2 7 11 15 target 9; 用双指针的话其实 11 15 这两个数字完全没有必要去遍历因为 其 已经 大于 target 了。且题目已经告知 说明没有负数那么说明这一部分可以舍去可以做一个裁剪把范围缩小把多余的右部分数组元素舍去减少 双指针法的 right 区间降低时间复杂度。 int GetRightIndex(vectorint nums, int target){int left 0;int right nums.size()-1;while(left right){int mid (left right) /2;if(nums[mid] target){left mid 1;}if(nums[mid] target){right mid;}}return right;}可以看到速度有效提升
三、代码实现
class Solution {
public:vectorint twoSum(vectorint nums, int target) {int left 0;int right GetRightIndex(nums, target);while(left right){if((nums[left] nums[right]) target){//说明右的数字太大了right--;}else if((nums[left] nums[right]) target){//左边的数字太小了left;}else{nums[0] nums[left];nums[1] nums[right];nums.resize(2);break;}}return nums;}int GetRightIndex(vectorint nums, int target){int left 0;int right nums.size()-1;int mid 0;while(left right){mid (left right) /2;if(nums[mid] target){left mid 1;}if(nums[mid] target){right mid;}}return right;}
};
