LeetCode刷题：第一题 两数之和

LeetCode刷题：第一题 两数之和

从今天开始刷LeetCode

第一题：两数之和

题目描述：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例：

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]


代码如下：

 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
 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> 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;
}

转载于:.html