menu 贺大礼(乱丶心)的博客
每日一题:1.两数之和
1244 浏览 | 2020-07-20 | 阅读时间: 约 1 分钟 | 分类: 算法,php,算法与数据结构,C/C++ | 标签: 算法
请注意,本文编写于 1427 天前,最后修改于 1250 天前,其中某些信息可能已经过时。

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum

PHP解法

class Solution {
/**
 * @param Integer[] $nums
 * @param Integer $target
 * @return Integer[]
 */
function twoSum($nums, $target) {
    $found = [];//找到的那个值,以找到的值为索引,原数组中的下标为值
    foreach ($nums as $key => $val) {
        $diff = $target - $val;//目标值减去数组中的一个值
        if (!isset($found[$diff])) {//
            $found[$val] = $key;
            continue;
        }
        return [$found[$diff], $key];
    }
}
}

C语言版
时间复杂度:O(n),
我们把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1) ,所以时间复杂度为 O(n)。
空间复杂度:O(n),
所需的额外空间取决于哈希表中存储的元素数量,该表中存储了 n 个元素。

struct hash_data{
    int key;
    int data;
    struct hash_data * next;
};
 struct hash_table
{
    struct hash_data ** head; //数组
    int hash_width;
};
///初始化
int hash_init(struct hash_table * table, int width){
    if(width<=0)
        return -1;
    struct hash_data **tmp = malloc(sizeof(struct hash_data *)*width);
    table->head = tmp;
    memset(table->head, 0, width * sizeof(struct hash_data *));
    if(table->head==NULL)
        return -1;
    table->hash_width = width;
    return 0;
}
///释放
void hash_free(struct hash_table table){
    if(table.head!=NULL){
        for (int i=0; i<table.hash_width; i++) {
            struct hash_data* element_head= table.head[I];
            while (element_head !=NULL) {
                struct hash_data* temp =element_head;
                element_head = element_head->next;
                free(temp);
            }
        }
        free(table.head);
        table.head = NULL;
    }
    table.hash_width = 0;
}

int hash_addr(struct hash_table table,int key){
    int addr =abs(key) % table.hash_width;
    return addr;
}

///增加
int hash_insert(struct hash_table table,int key, int value){
    struct hash_data * tmp = malloc(sizeof(struct hash_data));
    if(tmp == NULL)
        return -1;
    tmp->key = key;
    tmp->data = value;
    int k = hash_addr(table,key);
    tmp->next =table.head[k];
    table.head[k]=tmp;
    return 0;
}

///查找
struct hash_data* hash_find(struct hash_table table, int key){
    int k = hash_addr(table,key);
    struct hash_data* element_head=table.head[k];
    while (element_head !=NULL) {
        if ( element_head->key == key) {
            return element_head;
        }
        element_head = element_head->next;
    }
    return NULL;
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
      int* res = (int *)malloc(sizeof(int) * 2);
    * returnSize=0;
    struct hash_table table;
    hash_init(&table, 100);
    for(int i = 0; i < numsSize; I++)
    {
      int value = target - nums[I];
    struct hash_data* data=  hash_find(table, value);
        if (data !=NULL && data->data != i) {
            res[1]=I;
            res[0]=data->data;
            * returnSize=2;
            break;
        }
        hash_insert(table,nums[i] ,i);
    }
    hash_free(table);
    return res;
}
作者:chen-xing-15
链接:https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-san-chong-jie-fa-by-chen-xing-15/
来源:力扣(LeetCode)
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!