投票网站定制,小程序开发平台哪家比较不错,自己做网站要会什么软件,网站推广工作是在网站发布之后开展的目标#xff1a;
将LeetCode前300的简单题都刷一遍。将LeetCode Hot100的题都刷了。
两数之和
给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那两个整数#xff0c;并返回它们的数组下标。
你可以假设每种输入只会…目标
将LeetCode前300的简单题都刷一遍。将LeetCode Hot100的题都刷了。
两数之和
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那两个整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
思路
暴力for循环
因为题面上说了数组中同一个元素在答案里不能重复出现。意思就是譬如返回的答案为[0,1]不能返回[0,1]和[1,0] 以此为出发点当我们开双重for循环时第一层for循环的i从左到右遍历第二层的for循环的j就应该在i的右边开始遍历。因为如果j在i的左边开始遍历那么就相当于重复遍历因为i就是从左边遍历来的呀相当于之前遍历情况的i和j对调了。 时间复杂度On^2 空间复杂度O1
哈希表
由题意可得如果答案存在那么一定是成对存在的。 以此为出发点除了第一个数直接放入哈希表之外从数组第二个数开始遍历并同时构造哈希表。假设数组中被遍历的数为x如果target-x存在于哈希表中那么说明我们找到了这一对。直接输出即可。如果不存在于哈希表中那么将x作为keyx在数组中对应的下标作为value存到哈希表中。
时间复杂度On 空间复杂度On
C版本
暴力for循环
class Solution {
public:vectorint twoSum(vectorint nums, int target) {for(int i0;inums.size()-1;i){for(int ji1;jnums.size();j){if(nums[i]nums[j]target) {return {i,j};}}}return {};}
};哈希表
class Solution {
public:vectorint twoSum(vectorint nums, int target) {int len nums.size();unordered_mapint,inthashtable;hashtable[nums[0]]0;for(int i1;ilen;i){int another target-nums[i]; if(hashtable.contains(another)) {int idxhashtable.find(another)-second;return {i,idx};}else hashtable[nums[i]]i;}return {};}
};选择unordered_map的原因
选择umap的原因是查询单个key的效率比map高一般都能在常数时间内完成。但是查询某一范围内的key比map效率低。
unordered_map和相关用法
构造哈希表一般都用unordered_map 插入元素map[key]value 查询key的映射返回布尔值map.contains(key) 查询key的映射找到则返回指向该元素的迭代器否则返回指向end的迭代器map.find(key)
vector数组的构造
直接用{值}构造即可。
java版本
暴力for循环
class Solution {public int[] twoSum(int[] nums, int target) {int lennums.length;for(int i0;ilen-1;i){for(int ji1;jlen;j){if(nums[i]nums[j]target)return new int[]{i,j};}}return new int[0];}
}new int[0]
new int[0]表示的是长度为0的空数组其实null也可以。但是这里空数组会更贴切题意。
new int[]{值}
new int[] {值}可以直接构造数组。
哈希表
class Solution {public int[] twoSum(int[] nums, int target) {int lennums.length;MapInteger,Integermap new HashMap(len-1);map.put(nums[0],0);for(int i1;ilen;i){int another target-nums[i];if(map.containsKey(another)){return new int[]{i, map.get(another)};}map.put(nums[i],i);}return new int[0];}
}length
注意java中要求数组的长度是直接.length
HashMap相关方法
可以指定长度构造也可以不指定长度构造。这里是指定了长度的。 插入元素map.put(key, value1); 获取元素map.get(key1); 清空mapmap.clear(); 查询key的映射返回布尔值map.containsKey(key); 查询value的映射返回布尔值map.containsValue(value1);
python版本
暴力循环
class Solution(object):def twoSum(self, nums, target):n len(nums)for i in range(0, n-1):for j in range(i1, n):if nums[i]nums[j]target:return [i,j]return [] range的使用
别忘了……
哈希表
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:hashtable dict()for i, num in enumerate(nums):if target - num in hashtable:return [hashtable[target - num], i]hashtable[nums[i]] ireturn []hashtable
哈希表在python中用的是字典实现的。直接用dict()构造即可 查询key的映射key in hashtabe 插入数据hashtable[key]value
字典的构造
直接[key, value]就能构造
enumerate的使用
同时返回数据和数据下标
