保定 网站百度快照首页

哈希

128.最长连续序列

128. 最长连续序列 - 力扣（LeetCode）

这个题要求O(n)的时间复杂度，我一开始想的是双指针算法（因为我并不是很熟悉set容器的使用），但是双指针算法有小部分数据过不了。

题解给的哈希算法太妙了，简单来说就是通过unordered_set来去重，然后对于序列中的每一个元素num，使用count操作来查找序列中是否存在num-1，不存在的话，说明这个元素num是连续序列的首元素，最后比较得到最大值就行。

 set、multiset、map、multimap
特点：底层是红黑树，键值有序，set 、 map 键不可重复，multiset 和 multimap 可重复；
复杂度：插入、删除、查找都为O(logN)；

unordered_set，unordered_map，unordered_multiset，unordered_multimap
特点：底层实现是哈希表，键值无序，unordered_set 和 unordered_map 键不可重复，而另外两个可以重复；
复杂度：插入、删除、查找平均为O(1)，最坏为O(N)，空间换时间；

C++代码 

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int>num_set;for(auto &num:nums)num_set.insert(num);int ans=0;for(auto &num:num_set){if(num_set.count(num-1)==0){int cur=num;int curans=1;while(num_set.count(cur+1)){cur+=1;curans+=1;}ans=max(ans,curans);}}return ans;}
};

python代码

class Solution:def longestConsecutive(self, nums: List[int]) -> int:ans=0num_set=set(nums)for num in num_set:if num-1 not in num_set:cur_num=numcur_ans=1while cur_num+1 in num_set:cur_num+=1cur_ans+=1ans=max(ans,cur_ans)return ans

 双指针

283.移动零

283. 移动零 - 力扣（LeetCode）

方法一：用双指针算法把非0的元素移动到前面去，最后补0

class Solution {
public:void moveZeroes(vector<int>& nums) {int j=0;for(int i=0;i<nums.size();i++){if(nums[i]){nums[j++]=nums[i];}}for(int i=j;i<nums.size();i++){nums[i]=0;}}
};

 方法二：我也不知道题解怎么想出来的

class Solution {
public:void moveZeroes(vector<int>& nums) {int j=0;for(int i=0;i<nums.size();i++){if(nums[i]){int temp=nums[i];nums[i]=nums[j];nums[j]=temp;j++;}}}
};

python代码

class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""j=0for i in range(len(nums)):if nums[i]:nums[j],nums[i]=nums[i],nums[j]j+=1

11.盛最多水的容器 

11. 盛最多水的容器 - 力扣（LeetCode）

 这道题的最优解法是左右双指针法。双指针法的难点在于难于想到，难以证明。

 AcWing 1575. 从暴力优化到双指针，明明白白（图解） - AcWing

 移动短的一边是因为：如果移动长的一边,宽已经由短的一边固定了,长度在不断缩减,所以以后的面积只会比现在小；如果移动短的一边，即使长度变短了,但是宽度和长度的乘积可能会变大；最后就是将最大值返回

class Solution {
public:int maxArea(vector<int>& height) {int ans=-1;int i=0,j=height.size()-1;while(i!=j){ans=max(ans,(j-i)*min(height[i],height[j]));if(height[i]<height[j])i++;else j--;}return ans;}
};

python

class Solution:def maxArea(self, height: List[int]) -> int:ans=-1i=0j=len(height)-1while(i!=j):ans=max(ans,(j-i)*min(height[i],height[j]))if(height[i]<height[j]):i+=1else:j-=1return ans

 15.三数之和

15. 三数之和 - 力扣（LeetCode）

1. 排序：使用std::sort对数组进行排序。
2. 外层循环：从第一个元素开始，每次选择一个元素作为三元组的第一个数。
3. 内层循环：使用两个指针left和right从中间开始向两边扩展，寻找和为0的三元组。
4. 跳过重复元素：在添加三元组到结果数组之前，检查当前元素是否与前一个元素相同，如果是，则跳过当前元素，避免重复。

定一找二，变双指针

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {std::sort(nums.begin(), nums.end());vector<vector<int>> ans;int n = nums.size();for (int i = 0; i < n - 2; i++) {if (i && nums[i] == nums[i - 1]) continue; // 跳过重复的元素int left = i + 1, right = n - 1;while (left < right) {long long sum = nums[i] + nums[left] + nums[right];if (sum == 0) {ans.push_back({nums[i], nums[left], nums[right]});while (left < right && nums[left] == nums[left + 1]) left++; // 跳过重复的元素while (left < right && nums[right] == nums[right - 1]) right--; // 跳过重复的元素left++;right--;} else if (sum < 0) {left++;} else {right--;}}}return ans;}
};