leetCode-0001_两数之和

Posted on | In |

题目描述

英文题目

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
中文题目

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

1
2
3
4
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解决方法

方法一
  • 描述

为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。

通过以空间换取速度的方式，我们可以将查找时间从 O(n) 降低到 O(1)。哈希表正是为此目的而构建的，它支持以 近似 恒定的时间进行快速查找。我用“近似”来描述，是因为一旦出现冲突，查找用时可能会退化到 O(n)。但只要你仔细地挑选哈希函数，在哈希表中进行查找的用时应当被摊销为 O(1)。

一个简单的实现使用了两次迭代。在第一次迭代中，我们将每个元素的值和它的索引添加到表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元素（target - nums[i]target−nums[i]）是否存在于表中。注意，该目标元素不能是 nums[i]nums[i] 本身！

整个实现步骤为：先遍历一遍数组，建立HashMap映射，然后再遍历一遍，开始查找，找到则记录index。

  • 源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdlib.h>
#include <string.h>

struct object {
    int key;
    int value;
};

int compare(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), compare);
    
    int i = 0;
    int j = numsSize - 1;
    while (i < j) {
        int diff = target - objs[i].value;
        if (diff < objs[j].value) {
            while (--j > i && objs[j].value == objs[j + 1].value) {
                
            }
        }
        else if (diff > objs[j].value) {
            while (++i < j && objs[i].value == objs[i - 1].value) {
                
            }
        }
        else {
            int *ret = (int *)malloc(sizeof(int) * 2);
            ret[0] = objs[i].key;
            ret[1] = objs[j].key;
            return ret;
        }
    }
    
    return NULL;
}

void test()
{
    int arr[4] = { 2, 7, 11, 15 };
    int *ret = twoSum(arr, 4, 9);
    if (ret) {
        printf("%d->%d\n",ret[0],ret[1]);
    }
}

题目来源

Two Sum

两数之和