|
>
两数之和 I
给定一个已按照 非递减顺序排列 的整数数组numbers请你从数组中找出两个数满足相加之和等于目标数 target。
函数应该以长度为2的整数数组的形式返回这两个数的下标值。numbers的下标从1开始计数，所以答案数组应当满足1 <= answer[0]<answer[1]<= numbers.length.你可以假设每个输入 只对应唯一的答案，而且你 不可以重复使用相同的元素。
问题分析
"两数之和"是一个经典的编程问题，它要求我们从一个已按照非递减顺序排列的整数数组中找出两个数，使得它们的和等于给定的目标数。这个问题的一个关键点是，我们需要返回这两个数在数组中的下标，而不是这两个数本身。
解题思路
由于数组已经按照非递减顺序排列，我们可以使用双指针的方法来解决这个问题。我们初始化两个指针，一个指向数组的开始，一个指向数组的结束。然后，我们比较这两个指针指向的数的和与目标数的大小。如果和等于目标数，我们就找到了答案；如果和小于目标数，我们就将左指针向右移动；如果和大于目标数，我们就将右指针向左移动。我们重复这个过程，直到找到答案或者两个指针相遇。
程序展示：
以下是在VC6.0环境下运行调试的C语言程序：
#include <stdio.h>#include <stdlib.h>
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){ int left = 0, right = numbersSize - 1; while (left < right) { int sum = numbers[left] + numbers[right]; if (sum == target) { int* ret = (int*)malloc(sizeof(int) * 2); ret[0] = left + 1; ret[1] = right + 1; *returnSize = 2; return ret; } else if (sum < target) { left++; } else { right--; } } *returnSize = 0; return NULL;}
int main() { int numbers[] = {2, 7, 11, 15}; int numbersSize = sizeof(numbers) / sizeof(int); int target = 9; int returnSize; int* ret = twoSum(numbers, numbersSize, target, &returnSize); if (ret != NULL) { printf("%d %d\n", ret[0], ret[1]); free(ret); } return 0;}
程序测试：
运行上述代码，在VC6.0的环境下，可以得到如下的输出：
1 2
解释:2与7之和等于目标数9。因此 index1=1 2
这与题目给出的结果一致，说明我们的算法是正确的
代码获取：
我用夸克网盘分享了「20240120」，点击链接即可保存。打开「夸克APP」，无需下载在线播放视频，畅享原画5倍速，支持电视投屏。
链接：https://pan.quark.cn/s/013f6710f738
下期预告
下期我们将探讨另一个有趣的问题：
扰乱字符串
使用下面描述的算法可以扰乱字符串s得到字符串t:1.如果字符串的长度为1，算法停止
2.如果字符串的长度>1，执行下述步骤:
在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串s，则可以将其分成两个子字符串x和y，且满足s=x+y。随机决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这-步骤之后，s可能是s=x+y或者S=V+ Xo
·在x和y这两个子字符串上继续从步骤1开始递归执行此算法。
给你两个 长度相等 的字符串 s1和s2，判断 s2 是否是 S1 的扰乱字符串。如果是，返回 true;否则，返回 falseo
示例 1:
输入:s1="great"，s2="rgeat'
输出:true
敬请期待！
希望这篇文章对你有所帮助！如果你觉得有用，不妨分享给你的朋友，也欢迎关注我们的微信公众号“工控小新”，我们会持续更新更多的编程教学内容。谢谢你的阅读！
点赞加关注，学习不迷路
微信公众号｜工控小新
EPLAN电气绘图、TIA博图基础 、CAD、C语言教学、单片机基础、三菱PLC ... 每日持续更新中
发现“分享”和“赞”了吗，戳我看看吧
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
