题目描述🍗

输入一个递增排序的数组和一个数字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;
}

---

本篇完！🍗