当前位置:首页 > 算法 > 正文内容

(LeetCode刷题)1. 两数之和

chanra1n1年前 (2024-03-19)算法1290

题目

image.png


解答一:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    for (int i = 0; i < numsSize; ++i) {
        for (int j = i + 1; j < numsSize; ++j) {
            if (nums[i] + nums[j] == target) {
                *returnSize = 2;
                int* res = (int*)malloc(sizeof(int) * (*returnSize));
                res[0] = i;
                res[1] = j;
                return res;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}

非常简单的思路,使用两层循环对数组内的数进行两两相加,然后同target相比较。时间复杂度为O(n²)。

image.png

解答二:

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* ret = (int*)malloc(sizeof(int) * 2);
    *returnSize = 2;

    int hash[20011] = {0};

    for (int i = 0; i < numsSize; ++i) {
        long complement = target - nums[i];
        int index = ((complement + (long)1e9) % 20011);
        index = index < 0 ? index + 20011 : index; // ensure the index is positive

        if (hash[index]) {
            ret[0] = hash[index] - 1;
            ret[1] = i;
            return ret;
        }

        index = ((nums[i] + (long)1e9) % 20011); // similarly for nums[i]
        index = index < 0 ? index + 20011 : index;
        hash[index] = i + 1;
    }

    *returnSize = 0;
    return NULL;
}

此C函数首先创建一个大小为2的动态整形数组ret。然后,创建了大小为20011的哈希表,用于散列所有可能的输入。

然后,该函数遍历输入数组nums的每个元素。对于每个元素nums[i],首先计算其与目标数值的差值complement。然后,将差值加上后对20011取模得到哈希表的索引。取模是为了将任何在-到范围内的整数映射到一个正数索引。如果取模结果为负,为防止数组越界,需要加上模数以使得索引变为正数。

接下来,判断哈希表中该索引位置是否已有元素。如果有,说明找到了匹配项,将哈希表索引对应元素以及当前值所在的索引退回。接下来对nums[i]执行相等操作并存储到哈希表中,这是为了让后面的元素找到和为目标值的组合。

最后,如果在数组中没有找到匹配项,则将返回值的大小设为0,并返回NULL。

image.png

扫描二维码推送至手机访问。

版权声明:本文由我的FPGA发布,如需转载请注明出处。

本文链接:https://world.myfpga.cn/index.php/post/393.html

分享给朋友:

“(LeetCode刷题)1. 两数之和” 的相关文章

算法初步

算法初步

假设我让你计算1+2+3+...+5000等于多少,有两种常见的方法:    1、按部就班累加    2、使用公式,(首项+末项)*项数/2假设你使用第一种方法从头到尾不出错的计算,可能也需要几个小时才能计算出来,但是如...

纸牌均分问题的简单实现-贪心

纸牌均分问题的简单实现-贪心

有 N 堆纸牌,编号分别为 1,2,…, N。每堆上有若干张,但纸牌总数必为N 的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆...

二叉树的应用

二叉树的应用

(1)     创建一棵二叉树;(2)     二叉树的先序递归遍历;(3)     二叉树的中序递归遍历;(4)     二叉树的后序递归...

常见算法的C语言实现(带题目、分析和答案) 穷举 递归 迭代 递推 分治 回溯 动态规划 贪心

常见算法的C语言实现(带题目、分析和答案) 穷举 递归 迭代 递推 分治 回溯 动态规划 贪心

1.1   基本思想1.1.1  穷举穷举(又称枚举)算法的基本思想是从所有可能的情况中搜索正确的答案。a)      题一查找数组中的两个元素,它们的和等于给定的目标值。给定一个包含 n 个整数的数组和一个目标值,找出...

(LeetCode刷题)3. 无重复字符的最长子串

(LeetCode刷题)3. 无重复字符的最长子串

题目:解法一:class Solution(object):     def lengthOfLongestSubstring(self,s):        &nb...