网站建设吉金手指专业13,简历制作官网,手机百度seo怎么优化,公众号开发者id在哪里查看Problem: 剑指 Offer 57. 和为s的两个数字 文章目录 题目解析算法思路分析复杂度Code 题目解析 首先来讲解一下本题的思路 我们看到本题的意思很简单#xff0c;就是去这个nums这个数组中进行寻找#xff0c;如果找到了两个数相加之和为target的话#xff0c;那构成一个结果… Problem: 剑指 Offer 57. 和为s的两个数字 文章目录 题目解析算法思路分析复杂度Code 题目解析 首先来讲解一下本题的思路 我们看到本题的意思很简单就是去这个nums这个数组中进行寻找如果找到了两个数相加之和为target的话那构成一个结果集并返回 算法思路分析 接下去我们来分析一下本题的思路 暴力解法
首先第一种我们都会想到的就是【暴力求解】那就是使用两层for循环去一一地做匹配工作不过这种解法我们可想而知一定会超时所以这里不做过多的叙述
for(int i 0;i nums.size(); i)for(int j i 1;j nums.size(); j)利用单调性使用双指针算法进行求解
我们的话主要还是利用双指针的这种解法去解决本题一个left指针指向最左端一个right指针指向最右端通过前后遍历去寻找哪两个数可以构成结果为【target】 这里会出现三种情况首先是第一种若是我们碰到了nums[left] nums[right] target那此时我们就可以去做一个取巧的工作读者可以再去仔细地阅读一下本题的题目意思便可以知道这个数组序列是呈现递增排列的那么既然【2】和最大的【21】都比target要来得小了和【21】前面的这个几个数就要来得更小了此时我们无需再去多次一举进行比较。此时只需执行left 接下去我们再来考虑一下这个nums[left] nums[right] target的情况那我们知道这种情况也是不符合的但是呢再去进行判断的时候我们还可以做进一步的简化读者可以先行思考一下此时我们应该排除掉哪个数字呢那很明显就是这个【21】为什么呢想一下这个【21】和最小的【11】都会超过target了那么其余的【15】和【19】岂不是更加会超过了所以呢这个【21】我们应该将其舍去才对对应到代码即为right-- 那最后这一种的话就是找到了的情况此时我们只需返回这两个数据的结果集的即可 复杂度
时间复杂度: 考虑到最坏的情况即为我们在遍历寻找的时候两个左右指针相遇了即为没找到那也就是把这个序列遍历了一遍其时间复杂度 O ( n ) O(n) O(n) 空间复杂度: 没有开辟任何额外的空间所以空间复杂度为 O ( 1 ) O(1) O(1) Code 以下是代码展示 这里的话讲一下和这个{nums[left], nums[right]}可能有的小伙伴不是很清楚此属于 C初始化列表 的相关知识一般我们在LeetCode中返回两个数的集合时无需再去创建新的vector集合而是会通过隐式类型转换构成一个vector集合进行返回
class Solution {
public:vectorint twoSum(vectorint nums, int target) {int left 0, right nums.size() - 1;int sum 0;while(left right){sum 0;sum nums[left] nums[right];if(sum target){left;}else if(sum target){right--;}else{return {nums[left], nums[right]};}}return {-1, -1};}
};
