劍指offer之和為s的數(shù)組

1 問題

輸入一個遞增排序數(shù)組和數(shù)字和s,在數(shù)組里面找2個數(shù)，他們的和是s,如果有多對，只需要輸出一對。
比如數(shù)組{1, 2, 4, 7, 11, 15}，我們輸出4 ，11

 
2 思路

我們定義2個首尾指針，先是1+15，大于15，然后我們尾巴指針左移一下，然后就是1+11 小于15，然后首指針右移動一下，2+11，依次類推。

 
3 代碼實現(xiàn)

    #include <stdio.h>
    #include <stdlib.h>
     
    #define true 1
    #define false 0
     
    int findNumber(int *a, int len, int sum, int *num1, int *num2)
    {
        int result = false;   
        if (NULL == a || len < 1 || NULL == num1 || NULL == num2)
        {
            return result;
        }
        int start = 0;
        int end = len - 1;
        while (end > start)
        {
            *num1 = a[start];
            *num2 = a[end];
            int curSum = *num1 + *num2;
            if (curSum == sum)
            {
                result = true;
                break;
            }
            else if (curSum > sum)
            {
                --end;
            }
            else
            {
                ++start;
            }
        }
        return result;
    }
     
    int main()
    {
        int a[] = {1, 2, 4, 7, 11, 15};
        int num1 = 1;
        int num2 = 3;
        int result = findNumber(a, sizeof(a) / sizeof(int), 15, &num1, &num2);
        if (result == 1)
        {
            printf("the num1 is %d the num2 is %d\n", num1, num2);
        }
        else
        {
            printf("do not find the two number in numbers");
        }
        return 0;
    }


 
4 運行結果

the num1 is 4 the num2 is 11

 
5 代碼優(yōu)化

        while (end > start)
        {
            int curSum = a[start] + a[end];
            if (curSum == sum)
            {
                *num1 = a[start];
                *num2 = a[end];
                result = true;
                break;
            }
            else if (curSum > sum)
            {
                --end;
            }
            else
            {
                ++start;
            }
        }


 


 


作者：chen.yu
深信服三年半工作經(jīng)驗，目前就職游戲廠商，希望能和大家交流和學習,
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎入門進階人工智能(鏈接)