网站建设公司找上海站霸,中国最新消息,ueditor wordpress html被转义,无代码应用搭建平台文章目录1. 题目2. 解题1. 暴力解法2. 哈希法3. python3解答1. 题目
题目链接#xff1a;https://leetcode-cn.com/problems/two-sum/
给定一个整数数组 nums 和一个目标值 target#xff0c;请你在该数组中找出和为目标值的那 两个 整数#xff0c;并返回他们的数组下标。…
文章目录1. 题目2. 解题1. 暴力解法2. 哈希法3. python3解答1. 题目
题目链接https://leetcode-cn.com/problems/two-sum/
给定一个整数数组 nums 和一个目标值 target请你在该数组中找出和为目标值的那 两个 整数并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是你不能重复利用这个数组中同样的元素。
给定 nums [2, 7, 11, 15], target 9因为 nums[0] nums[1] 2 7 9
所以返回 [0, 1]2. 解题
1. 暴力解法
每个元素都跟后面的比较n2 复杂度
class Solution
{
public:vectorint twoSum(vectorint nums, int target) {int i,j;vectorint ans;for(i 0; i nums.size()-1; i){for(j i1; j nums.size(); j){if(nums[i]nums[j] target){ans.push_back(i);ans.push_back(j);return ans;}}}return ans;}
};2. 哈希法
利用unordered_map哈希查找先建立哈希表O(n)再查找O(n)
//哈希法
class Solution
{
public:vectorint twoSum(vectorint nums, int target) {int i, d;vectorint ans;unordered_mapint,int unomap;//unordered_map是哈希表for(i 0; i nums.size(); i)//建立哈希表unomap[nums[i]] i;//哈希数组下标是值存的原来的下标for(i 0; i nums.size(); i){d target - nums[i];if(unomap.find(d) ! unomap.end() unomap[d]i){//如果查找到了且不是同一个元素ans.push_back(i);ans.push_back(unomap[d]);break;}}return ans;}
};优化只需要一次遍历
class Solution { // 2020.10.3
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint,int m;int number;for(int i 0; i nums.size(); i){number target-nums[i];if(m.find(number) ! m.end())return {i, m[number]};m[nums[i]] i;}return {};}
};3. python3解答
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:dic {}for i in range(len(nums)):dic[nums[i]] ifor i in range(len(nums)):if (target-nums[i]) in dic and dic[target-nums[i]] i:return [i,dic[target-nums[i]]]return [-1,-1]我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
