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

绝地灬酷狼 2022-06-12 14:43 105阅读 0赞

## 题目描述 ##

**题目1：**

**输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。**

## 输出描述: ##

## 对应每个测试案例，输出两个数，小的先输出。 ##

class Solution \{

public:
        vector<int> FindNumbersWithSum(vector<int> array,int sum) {
    //复杂度为0(n)的做法是：定义两个指针，p1和p2，p1指向数组的开头，
    //p2指向数组的结尾，依次往中间靠，若p1与p2指向的值的和大于sum，则
    //执行p2--，若p1与p2指向的值的和小于sum，则执行p1++。若最后p1与p2
    //指向的值不等于sum，则返回为空，否则p1和p2所指向的两个数就是最小和为sum的两个数。
            int indexFront=0;
            int indexBehind=len-1;
            while((array[indexFront]+array[indexBehind])>sum)  
                indexBehind--;
            while((array[indexFront]+array[indexBehind])<sum)  
                indexFront++;
            if((array[indexFront]+array[indexBehind])!=sum)
                return vec;
            vec.push_back(array[indexFront]);
            vec.push_back(array[indexBehind]);
            return vec;
        }
    };

**题目:2：**

**输入一个正数s，打印出所有何为s的连续正数序列（至少含有两个数）。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出三个连续序列1~5、4~6和7~8。**

#include<iostream>
    using namespace std;
    
    void PrintContiousSequence(int small, int big)
    {
    	for (int i = small; i <= big; i++)
    		cout << i << " ";
    	cout << endl;
    }
    
    void FindContiousSequence(int sum)
    {
    	int small = 1;
    	int big= 2;
    	int middle = (sum + 1) / 2;   //保证和为sum中至少有两个数字
    	int curSum = small + big;
    	while (small < middle)
    	{
    		if (curSum == sum)
    			PrintContiousSequence(small,big); //打印
    		while (curSum > sum&&small < middle)
    		  {
    			curSum -= small;
    			small++;
    			if(curSum==sum)
    				PrintContiousSequence(small, big);
    		  }
    		big++;
    		curSum += big;
    	}	
    }
    
    int main()
    {
    	int sum;
    	cin >> sum;
    //连续正数序列，连续的，比如sum=8.没有连续满足和为8的数满足条件
    	FindContiousSequence(sum);
    }