1. Two Sum

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.

Example:

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

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

看到该题的第一个思路就是使用两重循环遍历整个数组,然而这样的时间复杂度太大,OJ无法通过。这种思路的弊端是每次确定数组中是否存在一个数x使得x + nums[i] = target都需要遍历整个数组,这样整个算法的时间复杂度是O(n^2)

另一种思路是使用hash表,这种思路可以一次定位是否存在数x使得x + nums[i] = target都需要遍历整个数组,这样可以将算法的时间复杂度降为O(n)

使用hash表的代码为:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#include <stdio.h>
#include <stdlib.h>

#define MAP_MAX_SIZE   1000
#define mod(x, y) (x < 0 ? ( x % y ) + y : x % y)

typedef struct MAP_ITEM MAP_ITEM;

// 定义MAP里面的节点
typedef struct MAP_ITEM {
    int key;
    int value;
    MAP_ITEM *next;
}MAP_ITEM;

// 定义HASH_MAP类型
typedef struct HASH_MAP {
    MAP_ITEM *head;
    MAP_ITEM *tail;
}HASH_MAP;

// 向HASH_MAP里面增添一个键值对
void HASH_MAP_PUT(HASH_MAP *hashMap, MAP_ITEM *mapItem) {
    int key = mod((*mapItem).key, MAP_MAX_SIZE); 
    // 因为数组中的元素可以为负数,target - nums[i]也有可能为负数,这与数组下标不能为负数相矛盾,
    // 因此通过mod将负数映射到正数域中。
    if (hashMap[key].head == NULL) {
        hashMap[key].head = mapItem;
        hashMap[key].tail = mapItem;
    }
    else {
        hashMap[key].tail->next = mapItem;
        hashMap[key].tail = mapItem;
    }
}


int* twoSum(int* nums, int numsSize, int target) {
    HASH_MAP hashMap[MAP_MAX_SIZE];
    memset(hashMap, 0, sizeof(HASH_MAP) * MAP_MAX_SIZE);
    MAP_ITEM *mapItem = (MAP_ITEM*)malloc(numsSize * sizeof(MAP_ITEM));
    memset(mapItem, 0, sizeof(MAP_ITEM) * numsSize);
    MAP_ITEM *tempMapItem = NULL;
    int i = 0, x = 0, y = 0;
    int tempKey = 0;
    int *result = (int*)malloc(2 * sizeof(int));
    // 由于提示:The returned array must be malloced, assume caller calls free().
    // 在主函数中free的对象result是通过malloc函数动态创建的,twoSum函数又将函数里的result
    // 赋值给了主函数里的result,如果两个result中的一个是通过int result[2]来声明的,
    // 一个是通过int* result = (int*)malloc(2 * sizeof(int))来声明的,那么在free的时候,
    // OJ会报“Runtime Error”错误。Debug的方式就是讲twoSum函数体内的result和主函数里的
    // result声明保持一致,根据提示,都需要通过malloc动态分配。
    for (i = 0; i < numsSize; i++) {
        mapItem[i].key = nums[i];
        mapItem[i].value = i;
        mapItem[i].next = NULL;
        HASH_MAP_PUT(hashMap, &mapItem[i]);
    }
    for (i = 0; i < numsSize; i++) {
        tempKey = mod((target - nums[i]), MAP_MAX_SIZE);
        tempMapItem = hashMap[tempKey].head;
        while (tempMapItem) {
            if (tempMapItem->value != i && tempMapItem->key + nums[i] == target) {
// 这个if里面的条件非常重要。当数组为[2,2,6],target=4,tempMapItem->value != i避免了在这种情况下输出结果为[0,0];
// 又因为在进行HASH MAP映射时采用了mod,因此存在不同的数组元素对应同一个键(key)的情况,比如当MAP_MAX_SIZE = 1000时,
// 数组为[-2,3,998,5]时,元素-2和998都对应key = 998,因此条件tempMapItem->key + nums[i] == target避免了key与数组元素
// 不对应的情况,比如key = 998本应对应数组中的998元素,但它也同时对应了-2这个元素,这种情况出现的原因是数组的下标不能为
// 负数,通过mod将负数映射到了正数域中。
                x = i + 1;
                y = (hashMap[tempKey].head->value) + 1;
                if (x && y && (x ^ y)) {
                    result[0] = x < y ? x : y;
                    result[1] = x + y - result[0];
                    result[0]--;
                    result[1]--;
                    return result;
                    //break;
                }
            }
            tempMapItem = tempMapItem->next;
        }
    }
    result[0]--;
    result[1]--;
    return result;
}

int main() {
    int nums[3] = { -8,2,-4 };
    int target = -6;
    int *result;
    int i;
    result = twoSum(nums, 3, target);
    printf("nums[%d] + nums[%d] = %d.\n", result[0], result[1], target);
    free(result);
    scanf_s("%d",&i);
}

注意:memset函数对数组而言只能用于置零(0)或置负一(-1)操作。因为memset函数是对单个字节操作如果你把int a[5] 置2;memset(a,2,sizeof(int )*5); 因为它是整数型数组有四个字节,而每个字节都被赋值为2;即数(例 int a[5])每个元素(如a[0])中的每个字节(整型数组每个元素含有四个直接)的值都被赋予成2,二进制表示及(00000010 00000010 00000010 00000010);所以输出十进制printf(" %d ",a[0])为33686018;所以不能用memset对数组置0与-1以外的数赋值,因为-1的二进制码为(11111111 11111111 11111111 11111111)置负一数不会改变。

上面程序中,需要两个循环,第一个循环先创建hash表,第二个循环开始寻找,其实时间复杂度还可以再降低,降低的方法是边创建hash表边查找。实现方法如下:

// 这一种方法一遍创建hash表,一遍查找,时间复杂度更低
int* twoSum2(int* nums, int numsSize, int target) {
    int *result = (int*)malloc(2 * sizeof(int));
    memset(result, 0, 2 * sizeof(int));
    HASH_MAP hashMap[MAP_MAX_SIZE];
    memset(hashMap, 0, sizeof(HASH_MAP) * MAP_MAX_SIZE);
    MAP_ITEM *mapItem = (MAP_ITEM*)malloc(numsSize * sizeof(MAP_ITEM));
    memset(mapItem, 0, numsSize * sizeof(MAP_ITEM));
    int i;
    int tempKey = 0;
    MAP_ITEM *tempMapItem = NULL;
    for (i = 0; i < numsSize; i++) {
        tempKey = mod(target - nums[i], MAP_MAX_SIZE);
        if (hashMap[tempKey].head == NULL) {
            mapItem[i].key = nums[i];
            mapItem[i].value = i;
            mapItem[i].next = NULL;
            HASH_MAP_PUT(hashMap, &mapItem[i]);
        }
        else {
            tempMapItem = hashMap[tempKey].head;
            while (tempMapItem) {
                if (tempMapItem->value != i && tempMapItem->key + nums[i] == target) {
                    // result[0] = i < tempMapItem->value ? i : tempMapItem->value;
                    // result[1] = (i + tempMapItem->value) - result[0];
                    result[0] = tempMapItem->value;
                    result[1] = i;
                    return result;
                }
                tempMapItem = tempMapItem->next;
            }
        }
    }
    return result;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

1 × 1 =

23 + = 28