题目
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [
2,
7,
11,
15], target =
9,
Because nums[
0] + nums[
1] =
2 +
7 =
9,
return [
0,
1].
我的思路
对输入的整型数组 nums[] 由小到大进行排序，得到 tmp[] 数组；取出数组 tmp[] 的最大值（由于 tmp[] 已经排好序，所以最大值位于数组的最右边），将最大值与 tmp[] 的其它值相加（其它值从左到右依次选取），判断结果是否等于 target；如果找到 tmp[] 数组中有两个值相加等于 target，那么把这两个值在原数组 nums[] 对应的两个索引提取出来即可。否则，忽略当前的最大值，并将前一个值作为此时数组 tmp[] 的最大值，重复步骤2，直到把所有值都遍历完为止。
代码
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(
int* nums,
int numsSize,
int target) {
int i, j, key;
int* res = (
int *)malloc(
2 * sizeof(
int));
int* tmp = (
int *)malloc(numsSize * sizeof(
int));
for(i =
0; i < numsSize; i++) {
*(tmp + i) = *(nums + i);
}
for(j =
1; j < numsSize; j++) {
key = *(tmp +j);
i = j -
1;
while(i >=
0 && *(tmp + i) > key) {
*(tmp + i +
1) = *(tmp + i);
i--;
}
*(tmp + i +
1) = key;
}
for(i = numsSize -
1; i >
0; i--) {
if(*(tmp + i) *
2 < target) {
break;
}
for(j =
0; j < i; j++) {
if(*(tmp + i) + *(tmp + j) > target) {
break;
}
if(*(tmp + i) + *(tmp + j) == target) {
int m =
0;
int n =
0;
for(m =
0; m < numsSize; m++) {
if((*(tmp + i) == *(nums + m)) || (*(tmp + j) == *(nums + m))) {
if(n ==
0) {
*res = m;
n++;
}
else {
*(res +
1) = m;
}
}
}
free(tmp);
tmp = NULL;
return res;
}
}
}
*res =
0;
*(res +
1) =
0;
free(tmp);
tmp = NULL;
return res;
}
