四川住房城乡建设厅网站首页,做网站有弹窗叫什么,深圳宝安网站建设工,济南建站详情两数之和 两数之和1 思路一 #xff08;简单突破#xff09;2 思路二 #xff08;进行优化#xff09;3 思路三 #xff08;哈希表 我还不会#xff09; 谢谢阅读Thanks♪(#xff65;ω#xff65;)#xff89;下一篇文章见#xff01;#xff01;#xff01; 两数… 两数之和 两数之和1 思路一 简单突破2 思路二 进行优化3 思路三 哈希表 我还不会 谢谢阅读Thanks♪(ω)下一篇文章见 两数之和
题目链接 1 思路一 简单突破
最简单的思想 遍历 从头开始逐个遍历。 首先选定 加数1 然后寻找 加数2 如果两者之和满足条件 target 。返回相应下标即可
int* twoSum(int* nums, int n, int target, int* returnSize) {for(int i 0;i n;i){//加数1 从头开始for(int j i 1;j n;j){//加数2 从加数1 后一位开始if(nums[i]nums[j] target){//满足条件即可返回对应下标int* a (int*)malloc(2*sizeof(int)) ;a[0] i;a[1] j;//返回的数组大小*returnSize 2;//返回数组return a;}}}//如果全不满足 返回NULL*returnSize 0;return NULL;
}提交 过啦
但是看看运算时间居然这么慢确实咱们的算法时间复杂度是O(n^2),不够快速。 才打败了 69% 的用户。我们不能满足当下让我们思考有没有其他思路。
2 思路二 进行优化
仔细想想上面的遍历属实比较费时间那我们如何改进它呢我的想法是从选择数上下手取消逐个遍历改用 二分查找。二分查找的效率比逐个遍历快许多。但是进行二分查找 的前提是 数组有序如果我们进行简单的排序那数组下标就被打乱了无法返回正确值。所以我们有必要创建一个新数组而且是二维数组储存值和对应下标然后不断将和与target 比较进行二分查找即可。
//qsort 的比较函数 注意我们传的数据类型是 int*
static int compare(int* n1 , int* n2){return n1[0] - n2[0] ;}
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {int n numsSize;int arr[n][2]; // 分别储存下标和值大小 保证同时移动// 将原数组的值以及它对应的下标存入临时数组中for (int i 0; i n; i) { arr[i][0] nums[i]; // 值arr[i][1] i; // 该值对应的下标}//排序qsort(arr,n,sizeof(arr[0]),compare);//二分寻找for(int i 0; i n;i){int left 0 ,right n-1;//区间[0 , n-1]while(left right){int mid (left right) / 2;//区间中点//检查是否和为target 并且 两数下标不能相同否则就是同一个数if(arr[mid][0] nums[i] target i ! arr[mid][1] ){*returnSize 2 ; //两个数//开辟两个int类型的空间int* ret (int*)malloc(sizeof(int)*2); //记录两个数下标ret[0] i;ret[1] arr[mid][1];return ret;}//如果大于target 则在小区间寻找else if(arr[mid][0] nums[i] target){right mid-1;}//如果小于target 则在大区间寻找else {left mid 1;}}}//没有找到*returnSize 0;return NULL;}提交 过啦 这下子打败了98%的用户。我们从 120 ms 一下子来到 8 ms。 时间复杂度来到O(nlogn). 简直就是飞机和马车的差距 那么问题来到为什么还有 2% 比我们快 我看了大佬们的代码使用到了哈希表 而我现在还不会哭了。 o(╥﹏╥)oo(╥﹏╥)o!o(╥﹏╥)oo(╥﹏╥)o!o(╥﹏╥)oo(╥﹏╥)o!
3 思路三 哈希表 我还不会
下面给大家看一下大佬的 0 ms 的代码。
#define HashSize 107 // 哈希表大小typedef struct Node { // 哈希结点int value; // 值int index; // 下标struct Node* next; // 下指针
}Node;int* twoSum(int* nums, int numsSize, int target, int* returnSize) {int n numsSize; // 数组长度Node* hash[HashSize]; // 哈希表for (int i 0; i HashSize; i) { // 初始化哈希表hash[i] (Node*)malloc(sizeof(Node));hash[i]-value hash[i]-index -1;hash[i]-next NULL;}for (int i 0; i n; i) { // 遍历一遍原数组int pos abs(target - nums[i]) % HashSize; // 找到target - nums[i]在哈希表中对应的位置Node* head hash[pos];while (head-next head-next-value ! target - nums[i]) head head-next; // 找该位置是否有target - nums[i]这个值if (head-next) { // 找到符合题意的值*returnSize 2;int* ans (int*)malloc(sizeof(int) * 2);ans[0] i; ans[1] head-next-index; // 写入答案for (int i 0; i HashSize; i) free(hash[i]);return ans;}pos abs(nums[i]) % HashSize; // 找到nums[i]在哈希表中对应的位置head hash[pos];while (head-next) head head-next; // 写在这个位置的末尾head-next (Node*)malloc(sizeof(Node));head-next-value nums[i]; // 写入该值head-next-index i; // 写入该值对应的下标head-next-next NULL;}for (int i 0; i HashSize; i) free(hash[i]);*returnSize 0;return NULL;
}作者星开祈灵
链接https://leetcode.cn/problems/two-sum/solutions/2326455/1-liang-shu-zhi-he-by-xing-kai-qi-ling-vxt6/
来源力扣LeetCode
著作权归作者所有。C语言的缺陷 需要手撕哈希表。 来看大佬 C 的代码,真的非常美观 美 帅 炸裂
class Solution {
public:vectorint twoSum(vectorint nums, int target) {mapint,int a;//提供一对一的hashvectorint b(2,-1);//用来承载结果初始化一个大小为2值为-1的容器bfor(int i0;inums.size();i){if(a.count(target-nums[i])0){b[0]a[target-nums[i]];b[1]i;break;}a[nums[i]]i;//反过来放入map中用来获取结果下标}return b;};
};作者陈乐乐
链接https://leetcode.cn/problems/two-sum/solutions/4361/liang-shu-zhi-he-by-gpe3dbjds1/
来源力扣LeetCode
著作权归作者所有。谢谢阅读Thanks♪(ω)
下一篇文章见
