杭州网站建设机构,网站音乐播放代码,新公司做网站怎么弄,移动端响应式布局一、提出问题 给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是#xff0c;数组中同一个元素在答案里不能重复出现。 你可以按…一、提出问题 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1 输入nums [2,7,11,15], target 9
输出[0,1]
解释因为 nums[0] nums[1] 9 返回 [0, 1] 。示例 2 输入nums [3,2,4], target 6
输出[1,2]示例 3 输入nums [3,3], target 6
输出[0,1] 提示 2 nums.length 104-109 nums[i] 109-109 target 109只会存在一个有效答案进阶你可以想出一个时间复杂度小于 O(n2) 的算法吗 二、解决问题
1、利用暴力枚举解决 1思路 这应该是最简单的思路即列出所有可能的组合然后判断这些组合的和是否符合条件。 2代码 /*** Note: The returned array must be malloced, assume caller calls free().*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize){for(int i0;inumsSize-2;i)for(int ji1;jnumsSize-1;j){if(nums[i]nums[j]target){int* retmalloc(sizeof(int)*2);ret[0]i;ret[1]j;*returnSize2;return ret;}}*returnSize0;return NULL;} 3复杂度 时间复杂度O(N^2)其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。空间复杂度O(1)。2、利用哈希表解决 1思路 注意到方法一的时间复杂度较高的原因是对于数组中的一个数x寻找 target - x 的时间复杂度过高。因此我们需要一种更优秀的方法能够快速寻找数组中是否存在目标元素。如果存在我们需要找出它的索引。 使用哈希表可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。 我们创建一个哈希表对于每一个 x我们首先查询哈希表中是否存在 target - x然后将 x 插入到哈希表中即可保证不会让 x 和自己匹配。 2代码 struct hashTable
{int key;int val;UT_hash_handle hh;
};struct hashTable* hashtable;struct hashTable* find(int ikey)
{struct hashTable* tmp;HASH_FIND_INT(hashtable, ikey, tmp);return tmp;
}void insert(int ikey, int ival)
{struct hashTable* it find(ikey);if (it NULL) {struct hashTable* tmp malloc(sizeof(struct hashTable));tmp-key ikey, tmp-val ival;HASH_ADD_INT(hashtable, key, tmp);}else {it-val ival;}
}int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{hashtable NULL;for (int i 0; i numsSize; i) {struct hashTable* it find(target - nums[i]);if (it ! NULL) {int* ret malloc(sizeof(int) * 2);ret[0] it-val, ret[1] i;*returnSize 2;return ret;}insert(nums[i], i);}*returnSize 0;return NULL;
} 3复杂度 时间复杂度O(N)其中 N 是数组中的元素数量。对于每一个元素 x我们可以 O(1)地寻找 target - x。空间复杂度O(N)其中 N是数组中的元素数量。主要为哈希表的开销。总结回顾
这是leetcode的第一道题首先我想到的就是双for循环解决由于比较熟悉C因此使用C语言来解答解答过程中对参数的含义稍微懵了一下不过看别人的答案明白了参数的含义以及应该如何返回。后来想到作为算法题应该可以更讲究技巧的果然高手们想到了哈希表。数据结构的知识已经还给老师了对于别人的代码里的哈希操作只是大概了解后续要恶补一下数据结构。另外对于时间复杂度、空间复杂度只有一个名词概念复杂度是怎么算怎么定义的呢也要认真学习一下。否则这些基本概念不熟悉就来刷题只能贻笑大方了。第一次刷题收获良多坚持每天至少刷一题吧不为别的就为了活动活动脑袋巩固一下语言知识。
