LeetCode1.两数之和-创新互联
题目链接:https://leetcode.cn/problems/two-sum/
成都创新互联公司长期为成百上千客户提供的网站建设服务,团队从业经验10年,关注不同地域、不同群体,并针对不同对象提供差异化的产品和服务;打造开放共赢平台,与合作伙伴共同营造健康的互联网生态环境。为辽宁企业提供专业的网站建设、网站制作,辽宁网站改版等技术服务。拥有10余年丰富建站经验和众多成功案例,为您定制开发。思路如下:
从前往后遍历 n u m s [ ] nums[\ ] nums[ ] 数组,对于每个元素 n u m s [ i ] nums[i] nums[i] 我们做两件事:
- 判断 t a r g e t − n u m s [ i ] target - nums[i] target−nums[i] 是否在哈希表中;
- 将 n u m s [ i ] nums[i] nums[i] 插入哈希表中;
由于数据保证有且仅有一组解,假设是 { j , i } ( j < i ) \left\{ j, i \right\}\ (jj,i} (j
由于只扫描一遍,且哈希表unordered_map
的插入和查询操作的复杂度是
O
(
1
)
O(1)
O(1),所以总时间复杂度是
O
(
n
)
O(n)
O(n)。
C++代码如下:
class Solution {public:
vectortwoSum(vector& nums, int target) {int n = nums.size();
unordered_maphash;
for (int i = 0; i< n; i++) {int x = target - nums[i];
if (hash.count(x)) return {hash[x], i};
hash[nums[i]] = i;
}
return {};
}
};
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
新闻标题:LeetCode1.两数之和-创新互联
网页URL:http://myzitong.com/article/cesoce.html