两数之和

题目描述

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

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

链接:https://leetcode-cn.com/problems/two-sum

题解

思路1:最简单的暴力搜索,两遍for循环。当然速度最慢。

 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
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i, j, *ret;

    ret = (int*)malloc(sizeof(int) * 2);
    if(ret==NULL)
    {
        *returnSize = 0;
        return NULL;
    }

    for(i = 0; i < numsSize-1; i++){
        for(j = i + 1; j < numsSize; j++){
        if(nums[i] + nums[j] == target){
            ret[0] = i;
            ret[1] = j;
            *returnSize = 2;
            break;
          }
        }
    }

    if(*returnSize == 2)
    {
        return ret;
    }
    else
    {
        free(ret);
        return NULL;
    }
}
思路2:哈希表,一遍插入一边寻找,
  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
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
typedef struct Node{
    int index;
    int data;
}Node;

typedef struct HashTable{
    Node *element;
    int size;
}HashTable;

HashTable * HashTableInit(int size){
    HashTable* table;

    if(size <= 0){
        return NULL;
    }

    table = (HashTable*)malloc(sizeof(HashTable));
    if(NULL == table){
        return NULL;
    }

    table->size = size;

    table->element = (Node*)malloc(sizeof(Node) * size);
    if(NULL == table->element){
        return NULL;
    }
    memset(table->element, 0xff, sizeof(Node) * size);
    return table;
}

static int HashAddrGet(int data, HashTable *table){
    int addr = data % table->size;
    return (addr >= 0) ? addr : addr + table->size;
}

void HashInsert(HashTable *table, int index, int data){
    int addr = HashAddrGet(data, table);
    while(table->element[addr].index != -1){
        addr = (addr + 1) % table->size;
    }
    table->element[addr].index = index;
    table->element[addr].data = data;
    return;
}

Node *HashFind(HashTable *table, int data){
    int tmp, addr;
    tmp = addr = HashAddrGet(data,table);

    do{
        if(table->element[addr].index == -1){
            return NULL;
        }
        if(table->element[addr].data == data){
            return &table->element[addr];
        }

        addr = (addr + 1) % table->size;
    }while(addr != tmp);
    return NULL;
}

void HashFree(HashTable *table){
    if(NULL == table){
        return;
    }
    if(NULL != table->element){
        free(table->element);
    }

    free(table);
    return;
}

#define MAX_TABLE_LEN 100000

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i;
    int *ret = NULL;
    HashTable *table = NULL;
    Node *node = NULL;

    ret = (int *)malloc(sizeof(int) * 2);
    if (NULL == ret) {
        *returnSize = 0;
        return NULL;
    }
    memset(ret, 0, sizeof(int) * 2);

    table = HashTableInit(MAX_TABLE_LEN);
    if(NULL == table){
        *returnSize = 0;
        return NULL;
    }

    for(i = 0; i < numsSize; i++){
        node = HashFind(table, target - nums[i]);
        if(node != NULL){
            ret[0] = node->index;
            ret[1] = i;
            break;
        }else{
            HashInsert(table, i, nums[i]);
        }
    }

    HashFree(table);
    *returnSize = 2;
    return ret;
}

C++解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        vector<int> result;

        for (int i = 0; i < nums.size(); i++) 
        {
            int numberToFind = target - nums[i];

            if (hash.find(numberToFind) != hash.end()) 
            {
                result.push_back(hash[numberToFind]);
                result.push_back(i);            
                return result;
            }

            hash[nums[i]] = i;
        }
        return result;
    }
};