专栏首页猿人谷和为S的两个数字VS和为s的连续正数序列

和为S的两个数字VS和为s的连续正数序列

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

例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。

思路整理一下:最初我们找到数组的第一个数字和最后一个数字。首先定义两个指针,第一个指针指向数组的第一个(也就是最小的)数字,第二个指针指向数组的最后一个(也就是最大的)数字。当两个数字的和大于输入的数字时,把较大的数字往前移动;当两个数字的和小于数字时,把较小的数字往后移动;当相等时,打完收工。这样扫描的顺序是从数组的两端向数组的中间扫描。

bool FindNumbersWithSum(int data[], int length, int sum, int *num1, int *num2)
{
    bool found = false;
    if(length < 1 || num1 == NULL || num2 == NULL)
        return false;
    
    int ahead = length - 1;
    int behind = 0;
    
    while(ahead > behind)
    {
        long long curSum = data[ahead] + data[behind];
        if(curSum == sum)
        {
            *num1 = data[behind];
            *num2 = data[ahead];
            found = true;
            break;
        }
        else if(curSum > sum)
            ahead--;
        else
            behind++;
    }
    return found;
}

 测试代码:

#include<iostream>
using namespace std;

bool FindNumbersWithSum(int data[], int length, int sum, int *num1, int *num2)
{
    bool found = false;
    if(length < 1 || num1 == NULL || num2 == NULL)
        return false;
    
    int ahead = length - 1;
    int behind = 0;
    
    while(ahead > behind)
    {
        long long curSum = data[ahead] + data[behind];
        if(curSum == sum)
        {
            *num1 = data[behind];
            *num2 = data[ahead];
            found = true;
            break;
        }
        else if(curSum > sum)
            ahead--;
        else
            behind++;
    }
    return found;
}

int main()
{
    int data[] = {1, 2, 4, 7, 11, 15};
    int length  = sizeof(data) / sizeof(int);
    
    int num1, num2;
    bool result = FindNumbersWithSum(data, length, 15, &num1, &num2);
    if(result)
    {
        cout<<"num1:"<<num1<<endl;
        cout<<"num2:"<<num2<<endl;
    }
    else
        cout<<"failed!"<<endl;
    
    return 0;
}

题目:输入一个正数S,打印出所有和为S的连续正数序列(至少有两个数)。例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以结果打印出3个连续序列1~5,4~6和7~8.

有了解决前面问题的经验,这里也考虑两个数small和big分别表示序列的最小值和最大值。

首先把small初始化为1,big初始化为2.如果从small到big的序列的和大于S,可以从序列中去掉较小的值,也就是增大small的值。

如果从small到big的序列的和小于S,可以增大big,让这个序列包含更多的数字。因为这个序列至少要有两个数字,我们一直增加small到(1+S)/2为止。

void FindContinuousSequence(int sum)
{
    if(sum < 3)
        return;
    
    int small = 1;
    int big = 2;
    int middle = (1 + sum) / 2;
    int curSum = small + big;
    
    while(small < middle)
    {
        if(curSum == sum)
            PrintContinuousSequence(small, big);
        
        while(curSum > sum && small < middle)
        {
            curSum -= small;
            small++;
            
            if(curSum == sum)
                PrintContinuousSequence(small, big);
        }
        
        big++;
        curSum += big;
        
    }
}

void PrintContinuousSequence(int small, int big)
{
    for(int i = small; i <= big; ++i)
        printf("%d ", i);
    printf("\n");
}

扩展:

2010年中兴面试题 编程求解: 输入两个整数 n 和 m,从数列1,2,3.......n 中 随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来。

#include<list>  
#include<iostream>  
using namespace std;  
  
list<int>list1;  
void find_factor(int sum, int n)   
{  
    // 递归出口  
    if(n <= 0 || sum <= 0)  
        return;  
      
    // 输出找到的结果  
    if(sum == n)  
    {  
        // 反转list  
        list1.reverse();  
        for(list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++)  
            cout << *iter << " + ";  
        cout << n << endl;  
        list1.reverse();      
    }  
      
    list1.push_front(n);      //典型的01背包问题  
    find_factor(sum-n, n-1);   //放n,n-1个数填满sum-n  
    list1.pop_front();  
    find_factor(sum, n-1);     //不放n,n-1个数填满sum   
}  
  
int main()  
{  
    int sum, n;  
    cout << "请输入你要等于多少的数值sum:" << endl;  
    cin >> sum;  
    cout << "请输入你要从1.....n数列中取值的n:" << endl;  
    cin >> n;  
    cout << "所有可能的序列,如下:" << endl;  
    find_factor(sum,n);  
    return 0;  
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 寻找和为定值的两个数

    题目:输入一个数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。 要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即...

    猿人谷
  • 求大于整数m且紧靠m的k个素数 及 判断一个数是否为素数的方法

    题目:   请编写一个函数void fun(int m,int k ,int xx[]),该函数的功能是:将大于整数m且紧靠m的k个素数存入xx所指的数组中。 ...

    猿人谷
  • 找出一个数组中出现次数最大的数

    描叙:一大堆数据里面,数字与数字之间用空格隔开,找出出现次数最多的一个数字的算法 #include<stdio.h> void FindMostTimesDi...

    猿人谷
  • Golang Leetcode 1005. Maximize Sum Of Array After K Negations.go

    更多内容请移步我的repo:https://github.com/anakin/golang-leetcode

    anakinsun
  • Python习题集(四)

    https://www.cnblogs.com/poloyy/category/1676599.html

    小菠萝测试笔记
  • codevs3002 石子归并 3

    题目描述 Description 有n堆石子排成一列,每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子,一次合并的代价为两堆石子的重量和w[i]+w...

    attack
  • 3002 石子归并 3

     时间限制: 1 s  空间限制: 256000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 有n堆石子...

    attack
  • Length of Last Word

    问题:最后一个单词的长度 分析,注意s=" a  b  "这种情况,从后遍历单词,遇到空格退出 class Solution { public: int...

    用户1624346
  • 数组查询问题-LeetCode 303、304、306

    给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。

    算法工程师之路
  • 【学术】试试这个!研究人员设计出了更好的推荐算法

    改进的推荐算法在评级数据“稀疏”的情况下尤其有效。 ? 亚马逊和Netflix等网站的推荐系统使用了一种名为“协同过滤”的技术。为了确定一个给定的客户可能喜欢...

    AiTechYun

扫码关注云+社区

领取腾讯云代金券