和为 s 的两个数字（和为 s 的连续正数序列）

题目

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

思路

　　我们先在数组中选择两个数字，如果它们的和等于输入的 s，我们就找到了要找的两个数字。如果和小于 s 呢？我们希望两个数字的和再大一点。由于数组已经排好序了，我们可以考虑选择较小的数字后面的数字。因为排在后面的数字要大一些，那么两个数字的和也要大一些，就有可能等于输入的数字 s 了。同样，当两个数字的和大于输入的数字的时候，我们可以选择较大数字前面的数字，因为排在数组前面的数字要小一些。

#include <iostream>

#include <vector>

using namespace std;

class Solution

{

    public:

        void find_num_with_sum(const vector<int> &v,const int &sum);

};

void Solution::find_num_with_sum(const vector<int> &v,const int &sum)

{

    if(v.size()<=||v.empty())

        return;

    vector<int>::const_iterator begin=v.begin();

    vector<int>::const_iterator end=--v.end();

    while(begin<end)

    {

        if((*begin+*end)==sum)

        {

            cout<<*begin<<'\t'<<*end<<endl;

            break;

        }

        else if((*begin+*end)<sum)

            ++begin;

        else

            --end;

    }

}

int main()

{

    vector<int> v{,,,,,};

    Solution s;

    s.find_num_with_sum(v,);

    return ;

}

code

class Solution {

public:

    vector<int> FindNumbersWithSum(vector<int> arr,int sum) {

        if(arr.size()==)

            return {};

        else if(arr[]>sum)

            return {};

        int i=,j=arr.size()-;

        vector<int> res;

        while(i<j)

        {

            if(arr[i]+arr[j]==sum)

            {

                res.push_back(arr[i]);

                res.push_back(arr[j]);

                break;

            }

            if(i<j&&arr[i]+arr[j]>sum)

                --j;

            if(i<j&&arr[i]+arr[j]<sum)

                ++i;

        }

        return res;

    }

};

题目

　　输入一个正数 s，打印出所有和为 s 的连续正数序列（至少两个数）

思路

　　考虑用两个数 small 和 big 分别表示序列的最小值和最大值。首先把 small 初始化为 1，big 初始化为 2。如果从 small 到 big 的序列的和大于 s，我们可以从序列中去掉较小的值，也就是增大 small 的值。如果从 small 到 big 的序列的和小于 s，我们可以增大 big，让这个序列包含更多的数字。因为这个序列至少要有两个数字，我们一直增加 small 到(1+s)/2 为止。

#include <iostream>

#include <vector>

using namespace std;

class Solution

{

    public:

        void find_sequence(const int &sum);

};

void Solution::find_sequence(const int &sum)

{

    if(sum<=)

        return;

    int small=;

    int big=;

    int middle=(sum+)/;

    int curr_sum=small+big;

    while(small<middle)

    {

        if(curr_sum==sum)

        {

            for(int i=small;i<=big;++i)

                cout<<i<<'\t';

            cout<<endl;

        }

        while(curr_sum<sum&&small<middle)

        {

            ++big;

            curr_sum+=big;

            if(curr_sum==sum)

            {

                for(int i=small;i<=big;++i)

                    cout<<i<<'\t';

                cout<<endl;

                break;

            }

        }

        curr_sum-=small;

        ++small;

    }

}

int main()

{

    Solution s;

    s.find_sequence();

    return ;

}

code2

class Solution {

public:

    vector<vector<int> > FindContinuousSequence(int sum) {

        if(sum<)

            return {};

        int smallNum=,bigNum=;

        vector<vector<int>> res;

        while(smallNum<bigNum)

        {

            int curSum=(smallNum+bigNum)*(bigNum-smallNum+)/;

            if(curSum<sum)

                ++bigNum;

            if(curSum==sum)

            {

                vector<int> tmp;

                for(int i=smallNum;i<=bigNum;++i)

                    tmp.push_back(i);

                res.push_back(tmp);

                ++smallNum;

            }

            if(curSum>sum)

                ++smallNum;

        }

        return res;

    }

};

拓展

　　通常用循环求一个连续序列的和，但每次操作后的序列和操作之前的序列比大部分都是一样的，只是增加或减少了一个数字，因此可以再之前的序列基础上求后一个序列。

巴特西

和为 s 的两个数字（和为 s 的连续正数序列）

题目

思路

题目

思路

拓展

最新文章

热门文章