【剑指offer】——和为s的序列

文章目录

    • 1、和为s的两个数字
    • 2、和为s的连续正数序列

1、和为s的两个数字

1、题目要求
输入一个递增排序的数组和一个数字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、题目分析
方法一:两层for循环来挨个比较
因为这种方法的时间复杂度太高了,达到了O(n^2)。太过于繁琐,我们在此就不多加讨论。代码实现如下:

vector<int> twoSum(vector<int>& arr, int target)
{
	vector<int> res;
	for (int i = 0; i < arr.size(); i++)
	{
		int sum = arr[i];
		for (int j = i+1; j < arr.size(); j++)
		{
			int temp = sum + arr[j];
			if (temp == target)
			{
				res.clear();
				res.push_back(arr[i]);
				res.push_back(arr[j]);	
				break;
			}
		}
	}
	return res;
}

方法二:利用二分查找
有了方法一的一个大概思路。我们想要降低其时间复杂度的话,其实就要牢牢抓住数组有序的特点使用二分查找来完成问题的求解。

  1. 首先一个for循环,固定住arr[i]。然后另外一个值other=target-arr[i]。
  2. 然后就是利用二分查找的方式去寻找符合条件的other值。找到就压入数组进行退出。注意!!!这个退出是指的退出程序而不是退出循环。
  3. 这样的时间复杂度是O(nlogn)

代码实现如下:

vector<int> twoSum1(vector<int>& arr, int target)
{
	int high = arr.size() - 1;
	vector<int> res;
	for (int i = 0; i < arr.size(); i++)
	{
		int other = target - arr[i];
		int index = i;
		while (index <= high)
		{
			int mid = (high - index + 1) / 2 + index;
			if (arr[mid] == other)
			{
				res.push_back(arr[mid]);
				res.push_back(arr[i]);
				return res;
			}
			else if (arr[mid] > other)
			{
				high = mid - 1;
			}
			else
				index = mid + 1;
		}
	}
	return res;
}

方法三:双指针的方式
要充分利用数组有序的特点。

  1. 定义两个指针head和tail分别指向数组的头部和尾部。并定义sum = arr[head]+arr[tail]
  2. 当发现sum>target的时候,需要减少sum的值,所以让tail–。head++同理
  3. 找到了相等的值就依次将arr[head]和arr[tail]压入数组返回即可。注意!!!找到了一定要使用break;
  4. 时间复杂度是O(n)

代码实现如下:

vector<int> twoSum2(vector<int>& arr, int target)
{
	vector<int> res;
	if (arr.size() == 0)
	{
		return res;
	}
	int head = 0;
	int tail = arr.size() - 1;
	while (head < tail)
	{
		int sum = arr[head] + arr[tail];
		if (sum > target)
		{
			tail--;
		}
		else if(sum < target)
		{
			head++;
		}
		else
		{
			res.push_back(arr[head]);
			res.push_back(arr[tail]);
			break;
		}
	}
	return res;
}
int main()
{
	vector<int> res;
	res.push_back(16);
	res.push_back(16);
	res.push_back(18);
	res.push_back(24);
	res.push_back(30);
	res.push_back(32);
	vector<int> a = twoSum2(res, 48);
	for (int i = 0; i < a.size(); i++)
	{
		cout << a[i]<<" ";
	}
	return 0;
}

2、和为s的连续正数序列

1、题目大意
输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。

序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

示例1:
输入:target = 9
输出:[[2,3,4],[4,5]]

示例2:
输入:target = 15
输出:[[1,2,3,4,5],[4,5,6],[7,8]]

2、题目分析
从题目要求里面我们可以看到,要求我们的返回值得是一个二维数组。所有我们得定义一个二维数组来保存最后返回的结果值。

  1. 还是使用两个for循环的暴力方法来求解问题。第一层循环i从1开始,循环的中止条件是i<=(target+1)/2。内层循环从j=i开始进行累加得到sum.。中止条件相同。
  2. 遇到sum > target的情况就清空一位数组,跳出第二个for循环。

具体的还是以具体的例子来加以说明:
在这里插入图片描述
代码实现:

vector<vector<int>> findContinuousSequence(int target)
{
	vector<vector<int>> result;
	vector<int> temp;

	for (int i = 1; i <= ((target + 1) / 2); i++)
	{
		int sum = 0;
		for (int j = i ; j <= ((target + 1) / 2); j++)
		{
			sum += j;
			temp.push_back(j);
			if (sum > target)
			{
				temp.clear();
				break;
			}
			else if(sum == target)
			{
				result.push_back(temp);
				break;
			}
		}
	}
	return result;
}
int main()
{
	vector<vector<int>> res;
	res = findContinuousSequence(9);
	for (int i = 0; i < res.size(); i++)
	{
		for (int j = 0; j < res[i].size(); j++)
		{
			cout << res[i][j]<<" ";
		}
		cout << endl;
	}
	return 0;
}

热门文章

暂无图片
编程学习 ·

JVM——Java的内存回收

Java引用的种类对于JVM的垃圾回收机制来说,如果一个对象,没有一个引用指向它,那么它就被认为是一个垃圾。那该对象就会回收。可以把JVM内存中对象引用理解成一种有向图,把引用变量、对象都当成有向图的顶点,将引用关系当成图的有向边(注意:有向边总是从引用变量指向被引…
暂无图片
编程学习 ·

SSCMS部署Linux

一、进入手册:https://sscms.com/ 二、在首页点击,如下位置:三、点击快速上手,进入页面如下:四、点击linux中运行SSCMS https://sscms.com/docs/v7/getting-started/using-linux.html#_1%E3%80%81%E5%AE%89%E8%A3%85%E4%BE%9D%E8%B5%96%E5%8C%85 根据里面的步骤一步步进行…
暂无图片
编程学习 ·

linux安装nginx及https化

Linux安装nginx安装操作系统:centos 安装前先确保系统安装了g++、gcc、openssl-devel、pcre-devel和zlib-devel软件yum install gcc-c++ yum -y install zlib zlib-devel openssl openssl--devel pcre pcre-devel上传nginx安装包nginx-1.13.0.tar.gz至linux指定位置(/usr/loc…
暂无图片
编程学习 ·

最长重复子数组(java)

问题描述: 给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。 样例: 代码见下: package Leetcode; import java.util.Scanner; public class FindLength {public static int findLength(int[] A, int[] B) {//暴力破解int len1=A.length;int len2=B.…
暂无图片
编程学习 ·

ITEST考试助手 --- 记一次我与ITEST的拉锯战

文章目录0x0 前言0x1 1.0版本 -- 解除限制我方进攻0x2 2.0版本 - 自动翻译与解析听力我方进攻ITEST方防御0x3 3.0版本 -- 解除切屏限制与添加翻译助手反制防御我方进攻ITEST防御0x4 4.0版本 - 全随机与ajax拦截反制防御我方进攻ITEST防御0x5 5.0版本 - 只读属性的胜利反制防御我…
暂无图片
编程学习 ·

js队列实现优先级插入的方法

队列是先进先出.在医院中排队的时候就是一个队列,最先排队的人,会先获得医生的治疗,这就是先进先出的队列但是也有例外,当医院来了一位急救病人的时候,这个队列就需要做一些改进,改为最小优先队列,这样可以让急救病人首先获得医生的救治,从而保住性命.现在用js来实现一个优先队…
暂无图片
编程学习 ·

防火墙中的DMZ区域,Trust区域,Untrust区域

** 区域的作用: ** 1.安全策略都基于区域实施 2.在同一区域内部发生的数据流动是不存在风险的,不需要实施任何安全策略。 只有当不同安全区域之间发生数据流动时,才会触发设备的安全检查,并实施相应的安全策略。 3.一个接口只能属于一个区域,而一个区域可以有多个接口。 *…
暂无图片
编程学习 ·

【整理】信息安全系统与技术课程复习整理

难得自己整理……信息系统安全与技术选择 15 填空 15 名词解释 4*6 简答 6*6 方案设计 10根据信息流动过程划分的安全威胁:中断威胁、截获威胁、篡改威胁、伪造威胁。 CIA安全需求模型:保密性(Confidentiality)、完整性(Integrity)、可用性(Availability)。 信息保障体…
暂无图片
编程学习 ·

vue项目实现路由按需加载(路由懒加载)的3种方式

vue异步组件es提案的import()webpack的require,ensure()vue异步组件技术 ==== 异步加载 vue-router配置路由 , 使用vue的异步组件技术 , 可以实现按需加载 . 但是,这种情况下一个组件生成一个js文件/* vue异步组件技术 */ {path: /home,name: home,component: resolve => re…
暂无图片
编程学习 ·

maven 有时候parent项目版本没更新的版本问题

对于parent工程,一般规定了版本,并且包含了子模块。如果首次编译整个项目,可能导致编译不成功,因为子模块需要父工程版本号。父工程想连同子模块一起编译,所以首次编译的时候,注释掉parent工程的子模块。先编译版本,成功后放开子模块。就可以了。如果parent的版本发生变…
暂无图片
编程学习 ·

Spring-boot 使用undertow代替tomcat

Undertow是Red Hat公司的开源产品, 是一款灵活的高性能Web服务器,它完全采用Java语言开发,可以直接嵌入到Java项目中使用,支持阻塞IO和非阻塞IO。由于Undertow采用Java语言开发。 Undertow在高并发业务场景中,性能优于Tomcat,对于并发要求不高的情况下,二者差别不大。 Un…
暂无图片
编程学习 ·

wafmng项目限频&&黑名单功能方案

wafmng项目限频&&黑名单功能方案 需求:在心跳接口 http://manager.waf.qiyi.domain/api/heartbeat 和初始化接口 http://manager.waf.qiyi.domain/api/init 中增加限频和黑名单规则配置功能,黑名单规则配置可以进行增删查改功能。 一、前端页面显示 在http://localho…
暂无图片
编程学习 ·

Node.js爬虫实验项目二(二)后续

登录与注册 随后我们开始设置登录与注册页面,我们需要设定一些制度,比如没有注册的用户不可以登陆,不登陆不可以查看数据。 在登陆和注册时也需要添加提示功能,类似于登录时的密码错误时提示,注册时两次密码不相同时提示等日常登录注册页面所需要的提示功能必须都具备。 登…
暂无图片
编程学习 ·

操作系统-中断

什么是中断?中断是改变处理器执行指令顺序的一种事件。 这样的事件与CPU芯片内外部硬件电路产生的电信号相对应。为什么需要中断?有了中断后,使CPU可以与其他设备并行工作,能有效提高CPU的利用率,改善系统性能,支持系统的异步性。中断的类型 分为 : 同步中断(内部中…
暂无图片
编程学习 ·

IDEA下载依赖到本地Maven仓库

1、https://mvnrepository.com/到网络仓库寻找对应的依赖2、复制依赖到项目的pom.xml中3、点击项目右侧的maven,此时会出现相应的dependence.4、点击下载选择download sources即可下载资源到本地仓库。
暂无图片
编程学习 ·

LeetCode题解(0888):公平的糖果交换(Python)

题目:原题链接(简单)解法 时间复杂度 空间复杂度 执行用时Ans 1 (Python) O(A+B)O(A+B)O(A+B) O(1)O(1)O(1) 3784ms (33.83%)Ans 2 (Python) O(A+B)O(A+B)O(A+B) O(B)O(B)O(B) 448ms (88.16%)Ans 3 (Python)LeetCode的Python执行用时随缘,只要时间复杂度没有明显差异,执行…
暂无图片
编程学习 ·

SpringBoot+RabbitMQ,保证消息100%投递成功并被消费

一、先扔一张图说明:本文涵盖了关于RabbitMQ很多方面的知识点, 如:消息发送确认机制消费确认机制消息的重新投递消费幂等性, 等等 这些都是围绕上面那张整体流程图展开的, 所以有必要先贴出来, 见图知意二、实现思路简略介绍163邮箱授权码的获取编写发送邮件工具类编写RabbitMQ…