20240326每日一题题解

Problem

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

Solution

题外话：这道题的输入输出格式对于C++极其不友好。所以为了编写C++的程序，略微将输入输出方式稍加改变，变成输入三行，第一行输入n，第二行输入num数组，用空格分隔，第三行输入一个数target。

读入所有的数据之后，我们使用两个变量进行枚举：

我们枚举\(i\in[0,n-1],j\in[i+1,n-1]\)，然后判断选择数对\((i,j)\)​时的两数a[i]+a[j]是否与target相等。

Code

#include<iostream>
using namespace std;

int n;
int num[100010];
int target;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>num[i];
	}
	cin>>target;
	
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			if(num[i]+num[j]==target)
			{
				cout<<i<<" "<<j<<endl;
			}
		}
	}
	
	return 0;
}

进阶

可以排序+二分，也可以用map。

下面使用STL容器中的map来实现在\(O(n\log n)\)的时间复杂度内完成这个任务。

#include<iostream>
#include<map>
using namespace std;

int n;
map<int,int>mp;
int target;
int main()
{
	cin>>n;
	for(int i=0,t;i<n;i++)
	{
		cin>>t;
		mp[t]=i;
	}
	cin>>target;
	
	for(auto it=mp.begin();it!=mp.end();it++)
	{
		if(mp.find(target-it->first)!=mp.end())
		{
			cout<<it->second<<" "<<mp.find(target-it->first)->second<<endl;
			return 0;
		}
	}
	
	
	
	return 0;
}