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.

Example

# foundtion to find the integers
def find_two_suitable_int(list, wanted_sum):

    # check error
    if len(list) <= 1:
        print "list too short to work on"
        return (None, None)

    # pointers
    head = 0
    tail = len(list) - 1

    # find the integers
    while (tail > head):
        sum = list[head] + list[tail]
        if sum == wanted_sum:
            return (list[head], list[tail])
        elif sum > wanted_sum:
            tail = tail - 1
        else:
            head = head + 1

    # shows that no integers are found
    print "can't find suitable integers"
    return (None, None)

# main testing, output should be 11 and 4
list = [1, 2, 4, 7, 11, 15]
(x, y) = find_two_suitable_int(list, 15)
if x: print "the two integers are %s and %s" % (x, y)
#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

如果输入的数组是没有排序的,但知道里面数字的范围,其他条件不变,
如何在O(n)时间里找到这两个数字?

关于第14题,

1.题目假定是,只要找出俩个数,的和等于给定的数,
其实是,当给定一排数,
4,5,7,10,12
然后给定一个数,22。
就有俩种可能了。因为22=10+12=10+5+7。
而恰恰与第4题,有关联了。望大家继续思考下。:)。

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

第一个数组向右扫描,第二个数组向左扫描。

Leave a Reply

%d bloggers like this: