/ find

# Interview Practice 14 - Find Integer With Wanted Sum

### Question

Given a sorted integer list and an integer, find two integer in the list such that the sum of the two integers equals the given integer. It is required that the time complexity must be O(n). For example, the sorted integer list is {1, 2, 4, 7, 11, 15} and an integer 15. The output is 4 and 11 since 4 + 11 = 15.

### Solution

Since the integer list is sorted, it is actually not that difficult. We have to create 2 pointers, 1 at the head and 1 at the tail. Check the sum of them if they equals the given integer. If not, there are 2 conditions: sum is greater or smaller than the integer. if greated, move the tail pointer backward, else move the head pointer forward.

# include <iostream.h> bool FindTwoNumbersWithSum ( int data[], // 已经排序的 数组 unsigned int length, // 数组长度 int sum, //用户输入的 sum int& num1, // 输出符合和等于sum的第一个数 int& num2 // 第二个数 ) { bool found = false; if(length < 1) return found; int begin = 0; int end = length - 1; while(end > begin) { long curSum = data[begin] + data[end]; if(curSum == sum) { num1 = data[begin]; num2 = data[end]; found = true; break; } else if(curSum > sum) end--; else begin++; } return found; } int main() { int x,y; int a[6]={1,2,4,7,11,15}; if(FindTwoNumbersWithSum(a,6,15,x,y) ) { cout<<x<<endl<<y<<endl; } return 0; }

### Extended Question

1.题目假定是，只要找出俩个数，的和等于给定的数，

4,5,7,10,12

2.第14题，还有一种思路，如下俩个数组：
1、 2、  4、7、11、15     //用15减一下为
14、13、11、8、4、 0      //如果下面出现了和上面一样的数，稍加判断，就能找出这俩个数来了。