技术标签: # 数据结构与算法刷题(C语言) 算法 c语言 链表 数据结构
给定一个整数数组 nums
和一个目标值 target
,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。例如,给定nums=[2,7,11,15]
,target=9
,返回结果为 [0,1]
。若没有答案,则返回 [-1,-1]
。题目要求设计 twoSum()
函数:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
… }
};
【输入形式】
每个测试用例由两行数据构成,第一行给出整数数组,元素之间以空格隔开,可以有重复元素;第二行给出求和的目标值。
【输出形式】
返回累加和为目标值的两个整数在数组中的下标值,不限顺序。若没有答案,则返回 [-1,-1]
。
要想找两数和为 target
的下标,不难想到用两重 for
循环来遍历数组 num
,第一个 for
循环用i遍历数组 num[0,...,cnt-2]
,第二个 for
循环用j遍历数组 num[i+1,...,cnt-1]
(其中 cnt
为数组 num
的长度),只要判断有没有 num[i]+num[j]==target
即可。有的话就输出其两个数的下标,停止遍历;没有的话输出-1 -1。【这里要注意的是 i≠j
。】
Dev-C++.
数组。
输入:数组 num
和两数和 target
。
输出:满足条件的数组下标 ind1
、ind2
,否组输出-1 -1。
ind1←1,ind2←1
cnt = num.lenght
for i ← 0 to cnt-2
for j ←i+1 to cnt-1
if num[i]+num[j] == target
ind1 ← i,ind2 ← j
end if
end for
end for
return ind1,ind2
bool TwoSum(int cnt, int &ind1, int &ind2) {
for (int i = 0; i < cnt - 1; i++) {
// 外循环是数组 num[0,...,cnt-2]
for (int j = i + 1; j < cnt; j++) {
// 内循环是数组 num[i+1,...,cnt-1]
if (num[j] == target - num[i]) {
// 如果找到符合条件的两个数,
就保存其下标,返回主函数
ind1 = i;
ind2 = j;
return true;
}
}
}
return false;
}
需要先在源代码目录下新建 in.txt
文件,在此文件下输入要测试的数据。
#include <iostream>
using namespace std;
int num[10001] = {
0}, target; // 文件读取数据存放
bool TwoSum(int cnt, int &ind1, int &ind2) {
// 找两个数字和为 target 的数组 num 下标的函数
for (int i = 0; i < cnt - 1; i++) {
// 外循环是数组 num[0,...,cnt-2]
for (int j = i + 1; j < cnt; j++) {
// 内循环是数组 num[i+1,...,cnt-1]
if (num[j] == target - num[i]) {
// 如果找到符合条件的两个数,就保存其下标,返回主函数
ind1 = i;
ind2 = j;
return true;
}
}
}
return false;
}
int main() {
cout << "\t\t第2题 - 两数和\n\n";
cout << "---------------------------------------------------\n\n";
freopen("in.txt", "r", stdin);
int cnt = 0, ind1 = -1, ind2 = -1; // 先初始化 -> 若找不到符合条件的两个数,就输出 -1 -1
while (cin >> num[cnt++]); // 从 in.txt 中读取所有数据
cnt--; // 因为 在读取数据时 cnt++ 多运行了一次,所以减 1 得到所有数据的长度
target = num[cnt-1]; // 读取数据中的最后一个数据是 target,取出来
cnt--; // 得到数组长度
TwoSum(cnt, ind1, ind2); // 调用函数找下标
cout << "样例输入:\n";
for (int i = 0; i < cnt; i++) cout << num[i] << " ";
cout << "\n" << target << "\n\n样例输出:\n";
cout << ind1 << " " << ind2 << "\n\n\n";
freopen("CON", "r", stdin); // 为了可直接查看exe可执行文件,需要将权限返回键盘
system("pause");
return 0;
}
测试1
a) 测试数据用例:
2 7 11 15
9
b) 测试数据用例1的特点:题目给定数据,测试能否正确找到下标。
c) 测试结果:
测试2
a) 测试数据用例:
2 7 11 15
10
b) 测试数据用例2的特点:此测试找不到下标,应该要输出-1 -1.
c) 测试结果:
测试3
a) 测试数据用例:
2 7 11 15 7
9
b) 测试数据用例3的特点:含有重复值,应该输出最先符合条件的两个数下标。
c) 测试结果:
这道题目目前用的是暴力求解的思想,时间复杂度为O(n2),虽然能够通过测试平台,但是其性能还能够优化,比如可以用哈希表来做,那么时间复杂度就可以优化到O(n)。目前暂不展示利用哈希表的做法。
文章浏览阅读1k次。1、HTML5 Web SQL 数据库 Web SQL 数据库 API 并不是 HTML5 规范的一部分,但是它是一个独立的规范,引入了一组使用 SQL 操作客户端数据库的 APIs。如果你是一个 Web 后端程序员,应该很容易理解 SQL 的操作。Web SQL 数据库可以在最新版的 Safari, Chrome 和 Opera 浏览器中工作。2、核心方法 以下是规范中定义的三个_方式准则的定义
文章浏览阅读4.1k次,点赞2次,收藏6次。spring Boot 中使用线程池异步执行多个定时任务在启动类中添加注解@EnableScheduling配置自定义线程池在启动类中添加注解@EnableScheduling第一步添加注解,这样才会使定时任务启动配置自定义线程池@Configurationpublic class ScheduleConfiguration implements SchedulingConfigurer..._springboot启动后自动开启多个线程程序
文章浏览阅读1.1k次。在项目的target文件夹下把之前"mvn clean package"生成的压缩包(我的是jar包)删掉重新执行"mvn clean package"再执行"mvn clean install"即可_mvn clean install有errors
文章浏览阅读974次。Navicat连接mysql数据库时,不断报1405错误,下面是针对这个的解决办法:MySQL服务器正在运行,停止它。如果是作为Windows服务运行的服务器,进入计算机管理--->服务和应用程序------>服务。如果服务器不是作为服务而运行的,可能需要使用任务管理器来强制停止它。创建1个文本文件(此处命名为mysql-init.txt),并将下述命令置于单一行中:SET PASSW..._nvarchar链接不上数据库
文章浏览阅读2.2k次。Python的requests模块是一个常用的HTTP库,用于发送HTTP请求和处理响应。_python requests 参数
文章浏览阅读2.7w次,点赞7次,收藏50次。APT攻击APT攻击是近几年来出现的一种高级攻击,具有难检测、持续时间长和攻击目标明确等特征。本文中,整理了近年来比较典型的几个APT攻击,并其攻击过程做了分析(为了加深自己对APT攻击的理解和学习)Google极光攻击2010年的Google Aurora(极光)攻击是一个十分著名的APT攻击。Google的一名雇员点击即时消息中的一条恶意链接,引发了一系列事件导致这个搜_2010谷歌网络被极光黑客攻击
文章浏览阅读1.1k次。JS代码 /** * 生命周期函数--监听页面加载 */ onLoad: function (options) { setTimeout( function(){ wx.showToast({ title: '黄菊华老师', }) },2000 ) },说明该代码只执行一次..._微信小程序 settimeout 向上层传值
文章浏览阅读48次。uploadify2.1.4如何能使按钮显示中文博客分类:uploadify网上关于这段话的搜索恐怕是太多了。方法多也试过了不知怎么,反正不行。最终自己想办法给解决了。当然首先还是要有fla源码。直接去管网就可以下载。[url]http://www.uploadify.com/wp-content/uploads/uploadify-v2.1.4...
文章浏览阅读9.6k次,点赞5次,收藏36次。戴尔服务器安装VMware ESXI6.7.0教程(U盘安装)一、前期准备1、下载镜像下载esxi6.7镜像:VMware-VMvisor-Installer-6.7.0-8169922.x86_64.iso这里推荐到戴尔官网下载,Baidu搜索“戴尔驱动下载”,选择进入官网,根据提示输入服务器型号搜索适用于该型号服务器的所有驱动下一步选择具体类型的驱动选择一项下载即可待下载完成后打开软碟通(UItraISO),在“文件”选项中打开刚才下载好的镜像文件然后选择启动_vmware-vcsa-all-6.7.0-8169922.iso
文章浏览阅读2k次。百度语音技术永久免费的语音自动转字幕介绍基于百度语音技术,识别率97%无时长限制,无文件大小限制永久免费,简单,易用,速度快支持中文,英文,粤语永久免费的语音转字幕网站: http://thinktothings.com视频介绍 https://www.bilibili.com/video/av42750807 ...
文章浏览阅读7.6k次,点赞2次,收藏9次。Instrumentation是一种直接修改程序二进制文件的方法。其可以用于程序的调试,优化,安全等等。对这个词一般的翻译是“插桩”,但这更多使用于软件测试领域。【找一些相关的例子】Dyninst可以动态或静态的修改程序的二进制代码。动态修改是在目标进程运行时插入代码(dynamic binary instrumentation)。静态修改则是直接向二进制文件插入代码(static b_dyninst
文章浏览阅读2.9k次。部署asp网站到云服务器 内容精选换一换通常情况下,需要结合客户的实际业务环境和具体需求进行业务改造评估,建议您进行服务咨询。这里仅描述一些通用的策略供您参考,主要分如下几方面进行考虑:业务迁移不管您的业务是否已经上线华为云,业务迁移的策略是一致的。建议您将时延敏感型,有快速批量就近部署需求的业务迁移至IEC;保留数据量大,且需要长期稳定运行的业务在中心云上。迁移方法请参见如何计算隔离独享计算资源..._nas asp网站