首页 > 试题广场 >

设计一个C语言函数int isSum(int a[],int

[问答题]

给定一个长度为n的且已经按升序排序的整形数组a[]，和一个整数x，设计一个C语言函数int isSum(int a[],int n,int x)，判断是否存在两个元素使它们之和为x，如果存在则返回0。否则-1，请尽可能减少时间复杂度，并用O(f(n))表示算法时间复杂度。

添加回答
简直头像 简直 
//借鉴本题回答中“天道酬勤~~”的思想
#include<stdio.h>
int isSum(int a[],int n,int x){
	int low=0,high=n-1;
	while(low<high){
		if(a[low]+a[high]>x)
			high--;
		else if(a[low]+a[high]<x)
			low++;
		else return 0;
	}
	return -1;
}
int main(){
	int a[]={1,3,5,6,12},n=5,x=12;
	if(isSum(a,n,x)==0)
		printf("YES!");
	else printf("NO!");
	return 0;
}

发表于 2020-04-07 17:31:18 回复(0)
天道酬勤～～头像 天道酬勤～～
从两边向中间扫描，若和大于x则右端向左移，小于x，左端向右移，
发表于 2019-12-09 15:25:17 回复(0)
柳隽琰头像 柳隽琰
遍历数组对于每个元素ai，并记录是否存在x-ai（用hashMap或数组可以实现O(1)查找）
时间复杂度为O（n）
编辑于 2019-03-09 17:14:15 回复(0)
lsjjj头像 lsjjj
#include<iostream>
#include<string>
using namespace std;
int bsearch(int a[],int n,int k,int i){//二分法查找
int lo=0,hi=n-1;
while(lo<hi){
int mid=(lo+hi)/2;
if(a[mid]>k){
hi=hi/2;
}
else if(a[mid]<k){
lo+=hi/2;
}
else{
if(mid!=i)
return 1;
    return 0;
}
}
return 0;
}
int search(int a[],int n,int k){
for(int i=0;i<n;i++){

if(bsearch(a,n,(k-a[i]),i)==1){//i保证不会出现重复使用数组中的元素
return 1;
}
}
return 0;
}
int main(){
int a[10]={1,2,3,4,5,6,7,8,9,10};
int b= search(a,10,4);
cout<<b;
}
发表于 2017-09-07 22:39:39 回复(0)
提交观点

问题信息

数组
上传者：城市里的养猫者
难度：
4条回答 1667浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号