凡科免费做的网站,软件销售具体怎么做的,盐城网站建设0515icp,wdcp备份网站解题思路#xff1a; \qquad 对每个数nums[i]#xff0c;仅需在数组中搜索target-nums[i]是否存在。
优化思路#xff1a; \qquad 首先能想到#xff0c;利用哈希表O(1)查询target-nums[i]。 \qquad 建立mapint, vectorint的表能够处理重复元素#x… 解题思路 \qquad 对每个数nums[i]仅需在数组中搜索target-nums[i]是否存在。
优化思路 \qquad 首先能想到利用哈希表O(1)查询target-nums[i]。 \qquad 建立mapint, vectorint的表能够处理重复元素保证找到所有解。但是能否进一步优化 \qquad 观察题目假设每个输入只有一种解对于nums[i] nums[j]的情况当遍历到nums[j]时只要二者的和目标即可直接输出无需再存入表中如果和不满足且后面存在合理的解那么无论输出i还是j都成立。所以建立的表无需处理重复的情况可建表mapint,int。 \qquad 到这里思路已经足够简洁但是能否进一步优化代码实现提高运行速度
优化代码 \qquad 1使用unordered_map。
mapunordered_map特点有顺序key升序元素排列无顺序实现方式红黑树哈希表散列表时间效率O(logn)O(1)存储效率接近100%表中存在未使用的值稳定性分析平衡二叉树十分稳定O(logn)不稳定最快O(1)最坏O(n)【冲突过多时】头文件mapunordered_map \qquad 注写题大多时候适用 unordered_map当对查询稳定性要求高、需要排序时用map。 \qquad 2虽然函数返回值为vectorint但已知返回长度可以不建立数组直接返回{num1,num2}。
vectorint twoSum(vectorint nums, int target) {unordered_mapint,int m;int n nums.size();for(int i 0; i n; i){if(m.count(target - nums[i]) 0){m[nums[i]] i;}else{return {i, m[target - nums[i]]};}}return {};}参考博客 https://blog.csdn.net/JCjunior/article/details/107471425 https://blog.csdn.net/qq_45890970/article/details/123955261
