Given a list of integers, return indices of two numbers such that they add up to a specific target.
- You can assume that each input could have exactly one solution.
- Indices are zero-based.
Example:
- Given nums = [2, 7, 11, 15], target = 9,
- Because nums[0] + nums[1] = 2 + 7 = 9,
- return [0, 1].
C Solution (HashTable):
struct He {
int val;
int ind;
struct He *next;
};
struct Ht {
int size;
struct He **list;
};
struct Ht *create(void) {
struct Ht *ht = malloc(sizeof(struct Ht));
ht->size = 1000;
ht->list = calloc(ht->size, sizeof(struct He *));
return ht;
}
int find(struct Ht *ht, int val) {
int ind = val % ht->size;
if (ind < 0) ind = -ind;
struct He *p = ht->list[ind];
while (p) {
if (p->val == val) return p->ind;
p = p->next;
}
return -1;
}
void insert(struct Ht *ht, int val, int index) {
int ind = val % ht->size;
if (ind < 0) ind = -ind;
struct He *p = malloc(sizeof(struct He));
p->val = val;
p->ind = index;
p->next = ht->list[ind];
ht->list[ind] = p;
}
int* twoSum(int* nums, int numsSize, int target) {
int *res = malloc(2 * sizeof(int));
struct Ht *ht = create();
insert(ht, nums[0], 0);
int i;
for (i = 1; i < numsSize; i++) {
int _ind = find(ht, target - nums[i]);
if (_ind != -1) {
res[0] = _ind;
res[1] = i;
break;
}
insert(ht, nums[i], i);
}
return res;
}
Python Solution:
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
ni = {}
for i, num in enumerate(nums):
if target - num in ni:
return (ni[target - num], i)
ni[num] = i
C Solution (Two Points):
void quick_sort(int *nums, int numsSize, int *inds) {
if (numsSize < 2) return;
int key = nums[numsSize - 1];
int i;
for (i = 0; i < numsSize - 1 && nums[i] < key; i++);
if (i == numsSize - 1) {
quick_sort(nums, numsSize - 1, inds);
return;
}
int j;
for (j = i + 1; j < numsSize - 1; j++) {
if (nums[j] < key) {
int tmp = nums[j];
nums[j] = nums[i];
nums[i] = tmp;
tmp = inds[j];
inds[j] = inds[i];
inds[i] = tmp;
i++;
}
}
nums[numsSize - 1] = nums[i];
nums[i] = key;
key = inds[numsSize - 1];
inds[numsSize - 1] = inds[i];
inds[i] = key;
quick_sort(nums, i, inds);
quick_sort(nums + i + 1, numsSize - i - 1, inds + i + 1);
}
int* twoSum(int* nums, int numsSize, int target) {
int *inds = malloc(numsSize * sizeof(int));
int i;
for (i = 0; i < numsSize; inds[i] = i, i++);
quick_sort(nums, numsSize, inds);
int *res = malloc(2 * sizeof(int));
int l, r;
for (l = 0, r = numsSize - 1; l < r;) {
if (nums[l] + nums[r] == target) {
res[0] = inds[l];
res[1] = inds[r];
return res;
}
if (nums[l] + nums[r] > target) {
r--;
}
else l++;
}
return res;
}
Python Solution:
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
d = {}
for i, num in enumerate(nums):
if target - num in d: return [d[target - num], i]
d[num] = i
Summary:
- If we think the complexity of HashTable is O(N), then the solutions are O(N).
- Except HashTable, we can also use the Brute Force whose complexity is O(N2), or sort it first and then use two points O(NlgN).
- The time consumed by C solution is 3ms, beat 90%.
- Hashtable C solution 3ms(90%), Sort and Two points solution 239ms(39%)
- Obviously hashtable is a much better way in two sum if the array is not sorted.
LeetCode: 1. Two Sum
近期评论