剑指offer之面试题41和为s的两个数字VS和为s的连续正数序列

Love The Way You Lie 2022-07-24 04:09 135阅读 0赞

问题一、**问题描述**：

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得他们的和正好是s。如果有多对数字的和等于s，输出任意一对即可。

**实现代码**如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <limits.h>
    bool findTwoNum(int *num,int len,int *rs,int k){
    	int pre = 0,last = len-1;
    	int sum;
    	while(last>pre){
    		sum = num[pre]+num[last];
    		if(sum==k){
    			rs[0]=num[pre];
    			rs[1]=num[last];
    			return true;
    		}else if(sum<k){
    			pre++;
    		}else if(sum>k){
    			last--;
    		}
    	}
    	return false;
    }
    int main(int argc, char *argv[])
    {
    	while(true){
    		int num[]={
    			1,2,2,3,4,5,6,6,7,8,9,9,9
    		};
    		int k ;
    		scanf("%d",&k);
    		int len=sizeof(num)/sizeof(int);
    		int rs[2];
    		bool b = findTwoNum(num,len,rs,k);
    		if(b){
    			printf("%d\t%d\n",rs[0],rs[1]);
    		}else{
    			printf("there is no two number meet the requirements!\n");
    		}
    	}
    	return 0;
    }

上面代码的时间复杂度是O(n)。

问题二、**问题描述**：

输入一个递增排序的数组和一个数字s，在数组中查找连续的n个数（n>=2），使得他们的和正好是s。

**实现代码**如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <limits.h>
    
    void printNum(int *num,int pre,int last){
    	int i;
    	for(i=pre;i<=last;i++){
    		printf("%d\t",num[i]);
    	}
    	printf("\n");
    }
    
    bool findTwoNum(int *num,int len,int k){
    	bool rs =false;
    	if(k<3){
    		return rs;
    	}
    	int pre = 0,last = 1;
    	int sum= num[pre]+num[last],mid=(1+k)/2;
    	while(pre<mid && last<len){
    		if(sum==k){
    			printNum(num,pre,last);
    			rs = true;
    		}
    		while(sum>k && pre<mid && last<len){
    			sum-=num[pre++];
    			if(sum==k){
    				printNum(num,pre,last);
    				rs = true;
    			}
    		}
    		sum+=num[++last];
    	}
    	return rs;
    }
    int main(int argc, char *argv[])
    {
    	while(true){
    		int num[]={
    			1,2,2,3,4,5,6,6,7,8,9,9,9
    		};
    		int k ;
    		scanf("%d",&k);
    		int len=sizeof(num)/sizeof(int);
    		bool b = findTwoNum(num,len,k);
    		if(b){
    			printf("Have number meet the requirements!\n");
    		}else{
    			printf("there is no number meet the requirements!\n");
    		}
    	}
    	return 0;
    }

**参考资料**：  
剑指offer  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51385690  
作者：WSYW126