代码如下：
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target) {
static int a[] = {}; for (int i = ; i < numsSize; i++) {
for (int j = i + ; j < numsSize; j++) {
if (nums[i] + nums[j] == target) {
a[] = i;
a[] = j;
return a;
}
}
}
return ;
}
这道题简单，就不做过多解释。
而另一种方法，则是用到基数排序
/*************************************************************************
> File Name: 1-1.cpp
> Author: Mr.Lee
> Mail: 18646139976@163.com
> Created Time: 五 5/10 11:10:39 2019
************************************************************************/ void radix_sort(int *arr, int *main_ind, int n) {
#define MAX_N 65536
#define MAX_M 32768
#define L(x) (x & 0xffff)
#define H(x) ((x >> 16) & 0xffff) int cnt[MAX_N] = {}, *p;
int *temp = (int *)malloc(sizeof(int) * n);
int *ind = (int *)malloc(sizeof(int) * n);
for (int i = ; i < n; i++) cnt[L(arr[i])] += ;
for (int i = ; i < MAX_N; i++) cnt[i] += cnt[i - ];
for (int i = n - ; i >= ; i--) {
temp[--(cnt[L(arr[i])])] = arr[i];
ind[cnt[L(arr[i])]] = i;
}
memset(cnt, , sizeof(cnt));
for (int i = ; i < n; i++) cnt[H(temp[i])] += ;
for (int i = MAX_M; i < MAX_M + MAX_N; i++) cnt[i % MAX_N] += cnt[(i - ) % MAX_N];
for (int i = n - ; i >= ; i--) {
arr[--cnt[H(temp[i])]] = temp[i];
main_ind[cnt[H(temp[i])]] = ind[i];
}
free(temp);
free(ind);
return;
} int *twoSum(int *nums, int numsSize, int target, int *returnSize) {
int *ind = (int *)malloc(sizeof(int) * numsSize);
radix_sort(nums, ind, numsSize);
int p = , q = numsSize - ;
while (nums[p] + nums[q] != target) {
if (nums[p] + nums[q] > target) --q;
else ++p;
}
int *ret = (int *)malloc(sizeof(int) * );
ret[] = ind[p];
ret[] = ind[q];
if (ret[] > ret[]) {
ret[] ^= ret[], ret[] ^= ret[], ret[] ^= ret[];
}
free(ind);
returnSize[] = ;
return ret;
}
还有一种方法，则是哈希表
/*************************************************************************
> File Name: 1-2.cpp
> Author: Mr.Lee
> Mail: 18646139976@163.com
> Created Time: 五 5/10 11:30:27 2019
************************************************************************/ typedef struct Data {
int val, ind;
} typedef struct HashTable {
Data *data;
int *flag;
int size;
} HashTable; HashTable *init(int n) {
HashTable *h = (HashTable *)malloc(sizeof(HashTable));
h->data = (Data *)malloc(sizeof(Data) * n);
h->flag = (int *)calloc(sizeof(int), (n / + ) );
h->size = n;
return h;
} int hash(int val) {
return val & 0x7fffffff;
} int check(HashTable *h, int ind) {
int x = ind / , y = ind % ;
return (h->flag[x] & (1LL << y)) != ;
} void set(HashTable *h, int ind, Data d) {
int x = ind / , y = ind % ;
h->data[ind] = d;
h->flag[x] |= (1LL << y);
return;
} void insert(HashTable *h, int ind, Data d) {
Data d = {val, val_ind};
int ind = hash(val) % h->size;
int time = ;
while (check(h, ind)) {
ind += (time * time);
ind %= h->size;
}
set(h, ind, d);
return;
} int query(HashTable *h, int val) {
int ind = hash(val) % h->size;
int time = ;
while (check(h, ind) && h->data[ind].val != val) {
ind += (time * time);
ind %= h->size;
}
if (check(h, ind)) return h->data[ind].ind;
return -;
} void clear(HashTable *h) {
if (h == NULL) return;
free(h->data);
free(h->flag);
free(h);
return;
} int *twoSum(int *nums, int numsSize, int target, int *returnSize) {
HashTable *h = init(numsSize * );
int *ret = (int *)malloc(sizeof(int) * );
for (int i = , ind; i < numsSize; i++) {
if ((ind = query(h, target - nums[i])) == -) {
insert(h, nums[i], i);
continue;
}
ret[] = ind;
ret[] = i;
break;
}
returnSize[] = ;
return ret;
}