【每日一题】周末问题合并帖

【周六】LeetCode 220. 存在重复元素 III

思路

这题请教了一下学长，确定就是一个滑动窗口的延伸，也是动态的查询一个区间，每次都判断区间边界一边的点是否符合，如果不符合，再看看边界另一边的点是否符合，如果两者有一个符合，则可以直接返回true，否则的话就继续向下寻找，直到找出符合条件的值即可

C++代码

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        typedef long long ll;
        multiset<ll> s;
        s.insert(1e18); s.insert(-1e18);
        for(int i=0,j=0;i<nums.size();i++)
        {
            if(i-j>k)   s.erase(s.find(nums[j++]));
            int x=nums[i];
            auto it =s.lower_bound(x);
            if(*it -x<=t)   return true;
            --it;
            if(x-*it<=t)    return true;
            s.insert(x);
        }
        return false;
    }
};

【周日】LeetCode 26. 删除有序数组中的重复项

思路

这题是个纯模拟题，直接暴力枚举判定出来把符合条件的数存进一个新的数组（空间换时间）即可

C++代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k=0;
        for(int i=0;i<nums.size(); i++)
            if(!i || nums[i] != nums[i-1])
                nums[k++]=nums[i];
        return k;
    }
};