leetcode 第1题 two sum

题目地址

https://leetcode.com/problems/two-sum/description/

题目描述

/*
 * @lc app=leetcode id=1 lang=c
 *
 * [1] Two Sum
 *
 * https://leetcode.com/problems/two-sum/description/
 *
 * algorithms
 * Easy (44.20%)
 * Total Accepted:    1.8M
 * Total Submissions: 4.1M
 * Testcase Example:  '[2,7,11,15]\n9'
 *
 * 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:
 *
 *
 * Given nums = [2, 7, 11, 15], target = 9,
 *
 * Because nums[0] + nums[1] = 2 + 7 = 9,
 * return [0, 1].
 *
 *
 */


/*
 * Note: The returned array must be malloced, assume caller calls free().
 */

思路1

给定一个数组,判断是否存在两个数相加等于target.最容易想到的解法是枚举法,即暴力破解尝试任何两个数相加判断是否等于target.

思路1实现代码

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
//a file named two-sum.c

#include <stdio.h>

int main(void)
{
    //int array[] = {1,90,2,6,7,11,15};
    int array[] = {2,7,11,15};
    int target = 9;
    int i, k, ifFound = 0;
    int num = sizeof(array) / sizeof(array[0]);
    for(i = 0; i < num; i++){
        for(k = i + 1; k < num; k++){
            if(array[i] + array[k] == target){
                ifFound = 1;
                printf("[%d,%d]\n",i,k);
                return 0;
            }
        }
    }
    if(ifFound == 0){
        printf("No found!\n");
    }
    return 0;
}

编译并运行:

haha@hello:~$ gcc -g -o two-sum two-sum.c
haha@hello:~$ ./two-sum
[0,1]
haha@hello:~$

思路2

思路1的解法用了双重for循环,时间复杂度是O(num^2),如果待排序的元素少的话,运行时间还能接受,元素很多的话,运行时间就不乐观了.
得想办法把时间复杂度降下来.遍历数组用target减去数组中的每一个数,判断差是否在数组中,可以明显地把时间复杂度降下来,线性时间
就可以解决问题,时间复杂度是O(num),即哈希法.

思路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
// a file named two-sum.c

#include <stdio.h>
#include <stdlib.h>

#define SIZE 50000

int hash(int key) {
    int r = key % SIZE;
    return r < 0 ? r + SIZE : r;
}

void insert(int *keys, int *values, int key, int value) {
    int index = hash(key);
    while (values[index]) {
        index++;
        index %= SIZE;
    }
    keys[index] = key;
    values[index] = value;
}

int search(int *keys, int *values, int key) {
    int index = hash(key);
    while (values[index]) {
        if (keys[index] == key) {
            return values[index];
        }
        index++;
        index %= SIZE;
    }
    return 0;
}

int* twoSum(int* nums, int numsSize, int target,int *returnSize) {
    int keys[SIZE];
    *returnSize = 2;
    int values[SIZE] = {0};
    for (int i = 0; i < numsSize; i++) {
        int complements = target - nums[i];
        int value = search(keys, values, complements);
        if (value) {
            int *indices = (int *) malloc(sizeof(int) * (*returnSize));
            indices[0] = value - 1;
            indices[1] = i;
            return indices;
        }
        insert(keys, values, nums[i], i + 1);
    }
    return NULL;
}
int main(void)
{
    int array[] = {2,7,11,15};
    int target = 9;

    //int array[] = {89,22,7,11,45,15};
    //int target = 56;

    int numsSize = sizeof(array) / sizeof(array[0]);
    int returnSize = 0;
    int *result = NULL;
    result = twoSum(array,numsSize,target,&returnSize);
    if(result == NULL){
        printf("No fonud!\n");
    }
    else{
        printf("[%d,%d]\n",result[0],result[1]);
        free(result);
    }
    return 0;
}

编译并运行:

haha@hello:~$  gcc -g -o two-sum two-sum.c
haha@hello:~$ ./two-sum
[0,1]
haha@hello:~$