【数据结构】和为s的数字

超、凢脫俗 2022-05-17 03:51 47阅读 0赞

## 一、题目：和为S的两个数字 ##

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

## 二、示意图： ##

![70][]

## 三、代码实现 ##

#include<iostream>
    using namespace std;
    /*
    题目：和为S的两个数字
    
    	输入一个递增的排序的数组和一个数字，在数组中查找两个数，
    	使得它们的和正好是S,如果有多对数字的和等于S，就任意输出一对即可
        author：  daiV
        
    	思路：
    			设置两个指针，一个指向数组的首元素p1，一个指向数组的最后一个元素p2，
    			当（*p1）+ （*p2） > S时，p2向前移动，
    			当（*p1）+ （*p2） < S时，p1向后移动
    			（*p1）+ （*p2） = S时，输出
    
    */
    
    bool FindNumsWithSum(int* data, int length, int sum, int *p1, int *p2)
    {
    	bool found = false;
    	if(data == NULL ||length <1 ||p1 ==NULL||p2 == NULL )
    	{
    		return found;
    	}
    
    	int first = 0;
    	int last = length - 1;
    	while(last>first)
    	{
    		long long CurSum =data[first]+data[last];
    		
    		if(CurSum == sum)
    		{
    			*p1 = data[first];
    			*p2 = data[last];
    			found = true ;
    			break;
    		}
    		else
    			if(CurSum > sum)
    				--last;
    			else  ++first;
    	}
    	return found;
    }
    
    
    int main()
    {
    	int data[] = {1,2,4,7,11,15};
    	int length = sizeof(data)/sizeof(data[0]);
    	int sum  = 15;
    	int * p1 = data;
    	int * p2 = data +length -1;
    	FindNumsWithSum(data,  length,  sum,  p1, p2);
    	cout<<*p1<<endl;
    	cout<<*p2<<endl;
    	
    	return 0;
    }

## 四、结果展示 ##

![70 1][]

[70]: /images/20220517/d7e47e0f2f144bc6b084e659415166f2.png
[70 1]: /images/20220517/64ce4763f2f54c83b9da7ef1b921586a.png