力扣刷题（自用）

哈希

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=0
        num_set=set(nums)

        for num in num_set:
            if num-1 not in num_set:
                cur_num=num
                cur_ans=1

                while cur_num+1 in num_set:
                    cur_num+=1
                    cur_ans+=1
                ans=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=0
        for i in range(len(nums)):
            if nums[i]:
                nums[j],nums[i]=nums[i],nums[j]
                j+=1