题目
思路
题目中得到的信息有
- 都是整数，并且可正可负，也可一个值包含多个；
- 只有一个正确的结果。
方法一
最直接的思路就是两重循环遍历，时间复杂度是O(n^2)，这样肯定不行。
方法二
由于是乱序的，1）可以先排序，2）然后再遍历一遍就可以找到结果。排序的话不能再原来的基础上进行，这样就破坏了下标顺序，因此需要申请额外的空间，用于保存他们的索引，然后再该空间上进行排序。时间复杂度是[排序O(logn) + 查找O(n)]，空间复杂度是O(n)。
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numSize, int target) {
int *tmp = (int *)malloc(sizeof(int) * numSize);//申请额外空间
for (int i = 0; i < numSize; i++)
tmp[i] = i; //初始化
for (int i = 1; i < numSize; i++) { //采用的是插入排序
int value = tmp[i];
int j;
for ( j = i - 1; j >= 0; j--) {
if (nums[value] < nums[tmp[j]]) {
tmp[j+1] = tmp[j];
} else {
break;
}
}
tmp[j+1] = value;
}
int i = 0, j = numSize - 1;
while (i < j) { //遍历寻找结果
int ret = nums[tmp[i]] + nums[tmp[j]] - target;
if (ret == 0)
break;
if (ret > 0) j--;
else
i++;
}
int *ret = NULL;
if (i < j) {
ret = (int *)malloc(2*sizeof(int));
if (tmp[i] < tmp[j]) {
ret[0] = tmp[i] + 1;
ret[1] = tmp[j] + 1;
} else {
ret[1] = tmp[i] + 1;
ret[0] = tmp[j] + 1;
}
}
free(tmp);
return ret;
}
结果
方法三
方法二是通过两个值找target，可以换个思路通过一个值和target找另一个值。这种思路需要额外的数据结构，该数据结构必须要满足1）值和下标都能保存；2）可以快速查找出是否包含指定值。hashmap满足该条件。以值作为key,下标作为value。由于hashmap不能有重复key，题目有是允许一个值包含多个，这样可以吗？
两种情况：1）所求的结果值都是一样的，这样的话一个在hashmap中，另一个还没有插入进去，就找到正确的结果了；2）不相等，并且一个值为多个相同值中的一个，这样会将多个相同值插入到hashmap中，但题目中说正确结果只有一个，因此这种情况不会出现，所以hashmap完全满足该题目。
c版本
//采用数组方式存储，冲突的解决是最简单的，线性增加
typedef struct node {
int index; //下标
int value; //值
}node;
//从hash中取特定值，若没有返回-1
int hash_get(node *hash, int numSize, int value) {
int i = (unsigned int)value % numSize;
while (hash[i].index != -1) {
if (hash[i].value == value)
break;
i = (i + 1) % numSize;
}
return hash[i].index;
}
//将值和下标放入到hash中
void hash_put(node *hash, int numSize, int value, int index)
{
int i = (unsigned int)value % numSize;
while (hash[i].index != -1) {
i = (i + 1) % numSize;
}
hash[i].index = index;
hash[i].value = value;
}
int* twoSum(int* nums, int numSize, int target) {
node *hash = (node *)malloc(numSize * sizeof(node));
for (int i = 0; i < numSize; i++)
hash[i].index = -1;
int index;
int *ret = NULL;
for (int i = 0; i < numSize; i++) {
index = hash_get(hash, numSize, target - nums[i]);
if (index == -1)
hash_put(hash, numSize, nums[i], i);
else {
ret = (int *)malloc(2*sizeof(int));
ret[0] = index + 1;
ret[1] = i + 1;
break;
}
}
free(hash);
return ret;
}
结果
java版本
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) { //一遍遍历
Integer value = map.get(target - nums[i]); //在hashmap中取值
if (value == null) //若没有，则插入
map.put(nums[i], i);
else { //有，则说明已经找到
int[] ret = new int[2];
ret[0] = value + 1;
ret[1] = i + 1;
return ret;
}
}
return null;
}
结果
