寻找和为定值的两个数

题目:输入一个数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。 要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。 例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。

解析:如果数组是无序的,先排序(n*logn),然后用两个指针i,j,各自指向数组的首尾两端,令i=0,j=n-1,然后i++,j--,逐次判断 a[i]+a[j]?=sum,如果某一刻a[i]+a[j]>sum,则要想办法让sum的值减小,所以此刻i不动,j--,如果某一刻 a[i]+a[j]<sum,则要想办法让sum的值增大,所以此刻i++,j不动。所以,数组无序的时候,时间复杂度最终为 O(n*logn+n)=O(n*logn),若原数组是有序的,则不需要事先的排序,直接O(n)搞定,且空间复杂度还是O(1),此思路是相对于上述 所有思路的一种改进。(如果有序,直接两个指针两端扫描,时间O(N),如果无序,先排序后两端扫描,时间O(N*logN+N)=O(N*logN),空间始终都为O(1))。

总结

  • 不论原序列是有序还是无序,解决这类题有以下三种办法:1、二分(若无序,先排 序后二分),时间复杂度总为O(n*logn),空间复杂度为O(1);2、扫描一遍X-S[i]  映射到一个数组或构造hash表,时间复杂度为O(n),空间复杂度为O(n);3、两个指针两端扫描(若无序,先排序后扫描),时间复杂度最后为:有序 O(n),无序O(n*logn+n)=O(n*logn),空间复杂度都为O(1)。
  • 所以,要想达到时间O(N),空间O(1)的目 标,除非原数组是有序的(指针扫描法),不然,当数组无序的话,就只能先排序,后指针扫描法或二分(时间n*logn,空间O(1)),或映射或 hash(时间O(n),空间O(n))。时间或空间,必须牺牲一个,自个权衡吧。
  • 综上,若是数组有序的情况下,优先考虑两个指针两端扫描法,以达到最佳的时(O(N)),空(O(1))效应。否则,如果要排序的话,时间复杂度最快当然是只能达到N*logN,空间O(1)则是不在话下。

这里假定数组已经是有序的,代码可以如下编写(两段代码实现):

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;
}

 测试代码:

 1 #include<iostream>
 2 using namespace std;
 3 
 4 bool find_num(int data[] , int length , int sum , int &first_num , int &second_num)
 5 {
 6     if(length < 1)
 7         return true;
 8 
 9     int begin = 0;
10     int end = length - 1;
11 
12     while(begin < end)
13     {
14         int current_sum = data[begin] + data[end];
15 
16         if(current_sum == sum)
17         {
18             first_num = data[begin];
19             second_num = data[end];
20             return true;
21         }
22         else if(current_sum > sum)
23             end--;
24         else 
25             begin++;
26     }
27     return false;
28 }
29 
30 int main()
31 {
32     int data[] = {1 , 2 , 4 , 7 , 11 , 15};
33     int length = sizeof(data)/sizeof(int);
34     int first_num = 0 ;
35     int second_num = 0;
36     int sum = 15;
37 
38     if(find_num(data , length , 15 , first_num , second_num))
39     {
40         cout<<first_num<<" "<<second_num<<endl;
41     }
42     else
43         cout<<"not exist!"<<endl;
44 
45     return 0;
46 }

寻找和为定值的多个数:

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

 1 #include<list>  
 2 #include<iostream>  
 3 using namespace std;  
 4   
 5 list<int>list1;  
 6 void find_factor(int sum, int n)   
 7 {  
 8     // 递归出口  
 9     if(n <= 0 || sum <= 0)  
10         return;  
11       
12     // 输出找到的结果  
13     if(sum == n)  
14     {  
15         // 反转list  
16         list1.reverse();  
17         for(list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++)  
18             cout << *iter << " + ";  
19         cout << n << endl;  
20         list1.reverse();      
21     }  
22       
23     list1.push_front(n);      //典型的01背包问题  
24     find_factor(sum-n, n-1);   //放n,n-1个数填满sum-n  
25     list1.pop_front();  
26     find_factor(sum, n-1);     //不放n,n-1个数填满sum   
27 }  
28   
29 int main()  
30 {  
31     int sum, n;  
32     cout << "请输入你要等于多少的数值sum:" << endl;  
33     cin >> sum;  
34     cout << "请输入你要从1.....n数列中取值的n:" << endl;  
35     cin >> n;  
36     cout << "所有可能的序列,如下:" << endl;  
37     find_factor(sum,n);  
38     return 0;  
39 }  

参考:http://blog.csdn.net/v_JULY_v/article/details/6419466

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏自学笔记

Sort Algorithm

生成随机的n个数量的数组,输出数组每一个元素的内容。测试排序算法使用的标准就是运行时间和排序的正确性,所以需要一个验证正确性和计算排序时间的:

6920
来自专栏算法修养

PAT 1012 数字分类 (20)

给定一系列正整数,请按要求对数字进行分类,并输出以下5个数字: A1 = 能被5整除的数字中所有偶数的和; A2 = 将被5除后余1的数字按给出顺序进行交错...

27750
来自专栏数据结构与算法

06:整数奇偶排序

06:整数奇偶排序 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定10个整数的序列,要求对其重新排序。排序要求: 1...

43360
来自专栏magicsoar

Effective Modern C++翻译(2)-条款1:明白模板类型推导

第一章 类型推导 C++98有一套单一的类型推导的规则:用来推导函数模板,C++11轻微的修改了这些规则并且增加了两个,一个用于auto,一个用于decltyp...

203100
来自专栏数据结构与算法

P3709 大爷的字符串题(50分)

题目背景 在那遥远的西南有一所学校 /*被和谐部分*/ 然后去参加该省省选虐场 然后某蒟蒻不会做,所以也出了一个字符串题: 题目描述 给你一个字符串a,每次询问...

35470
来自专栏mathor

KMP(2)

11840
来自专栏SeanCheney的专栏

《Pandas Cookbook》第03章 数据分析入门1. 规划数据分析路线2. 改变数据类型,降低内存消耗3. 从最大中选择最小4. 通过排序选取每组的最大值5. 用sort_values复现nl

16420
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第4章 NumPy基础:数组和矢量计算4.1 NumPy的ndarray:一种多维数组对象4.2 通用函数:快速的元素级数组函数4.3 利用数组进行数据处理4.

NumPy(Numerical Python的简称)是Python数值计算最重要的基础包。大多数提供科学计算的包都是用NumPy的数组作为构建基础。 NumPy...

48180
来自专栏技术沉淀

Python: 函数式编程

map()函数接收两个参数,一个是函数,一个是序列,map将传入的函数依次作用到序列的每个元素,并把结果作为新的list返回,比循环更简洁,更易读。

18440
来自专栏静默虚空的博客

排序五 简单选择排序

要点 简单选择排序是一种选择排序。 选择排序:每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。 简单排序处理流程 ...

21990

扫码关注云+社区

领取腾讯云代金券