剑指offer--和为s的数字

题目描述🍗

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

算法分析🍗

算法1：遍历所有的数字，查看其它(后面所有的)数字和当前数字相加是否为s。O(n^2)

//arr:数组起始地址
//len:数组长度
//s:需要的和
void SumTos(int* arr, int len, int s)//O(n^2)
{
    for (int i = 0; i < len; i++)//遍历所有数字
    {
        for (int j = i + 1; j < len; j++)//遍历i后面所有的数字
        {
            if (arr[i] + arr[j] == s)
                printf("%d+%d=%d\n",arr[i],arr[j],s);
        }
    }
}

int main()
{
    int arr[] = {1,2,4,7,8,11,15};
    int len = sizeof(arr) / sizeof(arr[0]);
    int s = 15;
    SumTos(arr,len,s);

    return 0;
}

算法2.利用数据有序，用两个下标，一个在最前面，另一个在最后面，两个值相加如果等于s即找到，如果小于s则前面的下标往后移，如果大于s则后面的下标前移。

//arr:数组起始地址
//len:数组长度
//s:需要的和
void SumTos(int* arr, int len, int s)//O(n)
{
    int low = 0;
    int high = len - 1;
    int sum;//和
    while (low < high)//输出所有和为s的数字
    {
        sum = arr[low] + arr[high];
        if (sum == s)
        {
            printf("%d+%d=%d\n", arr[low], arr[high], s);
            low++;
        }

        else if (sum < s)//low后移
            low++;
        else //sum>s ,high前移
            high--;
    }
}

int main()
{
    int arr[] = {1,2,4,7,8,11,15};
    int len = sizeof(arr) / sizeof(arr[0]);
    int s = 15;
    SumTos(arr,len,s);

    return 0;
}