LC1 两数之和

代码如下：

 1 /**
 2  * Note: The returned array must be malloced, assume caller calls free().
 3  */
 4 int* twoSum(int* nums, int numsSize, int target) {
 5     static int a[2] = {0};
 6     
 7     for (int i = 0; i < numsSize; i++) {
 8         for (int j = i + 1; j < numsSize; j++) {
 9             if (nums[i] + nums[j] == target) {
10                 a[0] = i;
11                 a[1] = j;
12                 return a;
13             }
14         }
15     }
16     return 0;
17 }

这道题简单，就不做过多解释。

而另一种方法，则是用到基数排序

 1 /*************************************************************************
 2     > File Name: 1-1.cpp
 3     > Author: Mr.Lee
 4     > Mail: 18646139976@163.com
 5     > Created Time: 五  5/10 11:10:39 2019
 6  ************************************************************************/
 7 
 8 void radix_sort(int *arr, int *main_ind, int n) {
 9     #define MAX_N 65536
10     #define MAX_M 32768
11     #define L(x) (x & 0xffff)
12     #define H(x) ((x >> 16) & 0xffff)
13 
14     int cnt[MAX_N] = {0}, *p;
15     int *temp = (int *)malloc(sizeof(int) * n);
16     int *ind = (int *)malloc(sizeof(int) * n);
17     for (int i = 0; i < n; i++) cnt[L(arr[i])] += 1;
18     for (int i = 1; i < MAX_N; i++) cnt[i] += cnt[i - 1];
19     for (int i = n - 1; i >= 0; i--) {
20         temp[--(cnt[L(arr[i])])] = arr[i];
21         ind[cnt[L(arr[i])]] = i;
22     }
23     memset(cnt, 0, sizeof(cnt));
24     for (int i = 0; i < n; i++) cnt[H(temp[i])] += 1;
25     for (int i = MAX_M; i < MAX_M + MAX_N; i++) cnt[i % MAX_N] += cnt[(i - 1) % MAX_N];
26     for (int i = n - 1; i >= 0; i--) {
27         arr[--cnt[H(temp[i])]] = temp[i];
28         main_ind[cnt[H(temp[i])]] = ind[i];
29     }
30     free(temp);
31     free(ind);
32     return;
33 }
34 
35 
36 
37 int *twoSum(int *nums, int numsSize, int target, int *returnSize) {
38     int *ind = (int *)malloc(sizeof(int) * numsSize);
39     radix_sort(nums, ind, numsSize);
40     int p = 0, q = numsSize - 1;
41     while (nums[p] + nums[q] != target) {
42         if (nums[p] + nums[q] > target) --q;
43         else ++p;
44     }
45     int *ret = (int *)malloc(sizeof(int) * 2);
46     ret[0] = ind[p];
47     ret[1] = ind[q];
48     if (ret[0] > ret[1]) {
49         ret[0] ^= ret[1], ret[1] ^= ret[0], ret[0] ^= ret[1];
50     }
51     free(ind);
52     returnSize[0] = 2;
53     return ret;
54 }

还有一种方法，则是哈希表

/*************************************************************************
    > 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 / 32 + 1) );
    h->size = n;
    return h;
}

int hash(int val) {
    return val & 0x7fffffff;
}

int check(HashTable *h, int ind) {
    int x = ind / 32, y = ind % 32;
    return (h->flag[x] & (1LL << y)) != 0;
}

void set(HashTable *h, int ind, Data d) {
    int x = ind / 32, y = ind % 32;
    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 = 1;
    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 = 1;
    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 -1;
}

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 * 3);
    int *ret = (int *)malloc(sizeof(int) * 2);
    for (int i = 0, ind; i < numsSize; i++) {
        if ((ind = query(h, target - nums[i])) == -1) {
            insert(h, nums[i], i);
            continue;
        }
        ret[0] = ind;
        ret[1] = i;
        break;
    }
    returnSize[0] = 2;
    return ret;
}