单纯想讨论算法。
1. sort (number ) , O(nlogn)
2. i = 0 : n-1
(2.1) if( number[i] ) > target ) goto end
(2.2) slack = target - number[i] ;
(2.3) search ( number + i + 1, number + n , i)
这种算法整体应该也还是 O(nlogn) , 概要约如下。
int number[] = {2,7,11,15} ;
int nsize = sizeof(number) / sizeof(number[0]);
int target = 9;
std::sort( number , number + nsize );
int idx1 , idx2 ; // store ans
for(int i = 0 ; i < nsize-1 ; ++i)
{
if( number[i] > target ) break; // can't find ans
slack = target - number[i] ;
int * find_rst = std::find( number + i + 1 , number + nsize , slack ) ;
if(find_rst != number + nsize) { // find ans
idx1 = i ;
idx2 = find_rst - number ;
break;
}
}
不知道有没有更好的作法？ 另若是改成 (3个数之合) , (4个数之合) 为target 的话 ,
我也死在墙上了 XD
※ 引述《ciphero (奶油焗蛋饺...:))》之铭言：
: 问题(Question)：
: 今天试着写了一下 LeetCode 这个网站里的题目
: 虽然是解得出来，但是也遇到一个疑问：
: 就是效能的拿捏，与程式合理性之间该如何平衡？
: 就拿这个例子来说：
: https://leetcode.com/problems/two-sum/
: 题目意思是说输入一个数字阵列 numbers，与一个目标数字 target，
: 如何在 numbers 中找到其中两个数字之和，刚好等于 target。
: 举例而言：
: Input: numbers={2, 7, 11, 15}, target=9
: 则答案就是：
: Output: index1=1, index2=2 (第1个数字(2) + 第2个数字(7) = 9)
: 题目有个前提假设：
: 输入的阵列 numbers 里面，必定有两个数字之和等于 target，所以不需要考虑错误处理
: 所以我写了下面第一版的程式：
: int* twoSum(int* nums, int numsSize, int target) {
: int i, j, *x;
: for(i = 1; i < numsSize; i++) {
: for(j = 0; j < i; j++) {
: if(nums[j] + nums[i] == target) {
: x = malloc(2 * sizeof(int));
: x[0] = j+1; /* index1 */
: x[1] = i+1; /* index2 */
: return x;
: }
: }
: }
: }
: 这是一个用暴力法去寻找所有两个数字的组合，所以 time complexity = O(N^2)
: 后来觉得太慢了，就写了下面的第二版：
: int* twoSum(int* nums, int numsSize, int target) {
: int i, diff;
: int x[200001] = {0}; /* 位置 0~200000 表示 -100000~100000 之间的数字 */
: int *y;
: for(i = 0; i < numsSize; i++)
: x[nums[i] + 100000] = i + 1; /* 储存位置，若为 0 表示不存在 */
: for(i = 0; i < numsSize; i++) {
: diff = target - nums[i];
: if((x[diff + 100000] != 0) && (i + 1 != x[diff + 100000])) {
: y = malloc(2 * sizeof(int));
: y[0] = i + 1; /* index1 */
: y[1] = x[diff + 100000]; /* index2 */
: return y;
: }
: }
: }
: 原理是利用类似 Hash 的方法，对于有出现的数字，先储存其位置到一个阵列中。
: 当已知某一数字，又知道 target 时，就可以相减而得知缺哪个数字，
: 再去查询该数字是否存在，以及其位置。
: 这种方法的 time complexity 就比刚刚的第一版小很多
: but......
: 问题来了......
: 第二版的程式虽然效能快很多，但对于运算数字的大小有其限制。
: 至少我在上面的程式码之中，是假设数字应该只会出现在 -100000~100000 的范围之内
: 如果这样的程式题目出现在应征工作时，这样写是否恰当？
: 毕竟我觉得就工作而言，任何情况都有可能发生，
: 或者应该其实别想这么多，只要程式能够 work 就行？
: (至少这个版本，我在 LeetCode 里面是有通过验证的)
: 想请教各位高手，对于这一点的看法...
: 谢谢！