lecode练习（一）
两数之和
暴力解法
- c++
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
int i,j;
for (i=0;i<=nums.size()-1;i++)
{
for(j=i+1;j<nums.size();j++)
{
if(nums[i]+nums[j]==target)
{
return{i,j};
}
}
}
return {};
};
};
- python
class Solution:
def twoSum(self,nums,target):
for i in range(len(nums)-1):
num1=nums[i]
for j in range (i+1,len(nums)):
if num1+nums[j]==target:
return [i,j]
哈希表
hashtable的本质是一个数组。
类似要在字典里找到“王”字。通过他的首字母找到W，再根据W找到在第542页，再根据542找到“王”字。
哈希函数：根据某种规则找到他的键值，eg：找到王字的首字母
entry 键值：hash后找到的地址，类似字典的首字母搜索，eg：W
key关键字：entry后找到的地址，类似根据W找到的汉字页码，eg：p542
value值：key对应的值，类似根据页码找到的汉字，eg：王
哈希冲突：一个entry可能有多个key，类似W开头的汉字很多，搜的时候会有冲突，eg：吴
解决哈希冲突的方法：开放寻址法（寻找下一个可用地址），拉链法（结合链表）
扩容问题：每当hashtable容量占到75%，就会扩容为原来的2倍，然后把所有的entry重新hash一次放进新数组。
- c++
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashtable.find(target - nums[i]);//看看hash表里有没有符合要求的数字
if (it != hashtable.end()) {
return {it->second, i};//存对应值和下标
}
hashtable[nums[i]] = i;
}
return {};
}
};
过程 :
nums[3,4,5,2] target=6
i=0
hash [(3,0)]
i=1
it=6-4=2(is not in hashtable)
hash [(30,),(4,1)]
i=2
it=6-5=1(is not in hashtable)
hash [(3,0),(4,1),(5,2)]
i=3
it=6-2=4(is in hashtable(value=1))
return[1,3]//返回hash表里key=4的value 和 i
- python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:#这里的 -> 为函数添加元数据，描述函数的返回类型
hashtable = dict()
for i, num in enumerate(nums): #enumerate使num表示i为下标对应的值
if target - num in hashtable:
return [hashtable[target - num], i]
hashtable[nums[i]] = i
return []