两数之和
方案一
原数组排序,我们用两个指针分别指向数组首尾两个数,如果两个数和正好为target,则将这两个数一起存入结果中。然后就是跳过重复数字的步骤了,两个指针都需要检测重复数字。如果两数之和小于target,则我们将左边那个指针i右移一位,使得指向的数字增大一些。同理,如果两数之和大于target,则我们将右边那个指针j左移一位,使得指向的数字减小一些。
C-源代码
#include <stdlib.h>
#include <string.h>
struct object {
int key;
int value;
};
int compareObject(const void *a, const void *b) {
return ((struct object*)a)->value - ((struct object*)b)->value;
}
int* twoSum(int* nums, int numsSize, int target) {
struct object *objs = (struct object*)malloc(sizeof(*objs) * numsSize);
for(int i = 0; i < numsSize; i++) {
objs[i].key = i;
objs[i].value = nums[i];
}
qsort(objs, numsSize, sizeof(*objs), compareObject);
int left = 0;
int right = numsSize - 1;
while (left < right) {
int diff = target - objs[left].value;
if (diff < objs[right].value) {
while (--right > left && objs[right].value == objs[right + 1].value) {
}
}
else if (diff > objs[right].value) {
while (++left < right && objs[left].value == objs[left - 1].value) {
}
}
else {
int *ret = (int *)malloc(sizeof(int) * 2);
ret[0] = objs[left].key;
ret[1] = objs[right].key;
return ret;
}
}
return NULL;
}
void test_0001() {
int nums[5] = { 2, 7, 11, 15 };
int target = 9;
int *ret = twoSum(nums, sizeof(nums) / sizeof(nums[0]), target);
printf("%d->%d\n",ret[0],ret[1]);
}
C++实现
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
vector<int> res;
for (int i = 0; i < nums.size(); ++i) {
m[nums[i]] = i;
}
for (int i = 0; i < nums.size(); ++i) {
int t = target - nums[i];
if (m.count(t) && m[t] != i) {
res.push_back(i);
res.push_back(m[t]);
break;
}
}
return res;
}
};
网友评论