题解

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]));
                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;
    }
};

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        for (int i = 0; i < nums.size(); i ++ )
        {
            int x = nums[i];
            if (mp.count(x) && abs(i - mp[x]) <= k )    return true;
            mp[x] = i; 
        }
        return false;
    }
};

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> S;
        for (auto &x : nums)
        {
            // 说明x之前已经出现过   那么在此时又遍历到x  因此x至少出现了两次
            if (S.count(x) )    return true;
            S.insert(x); 
        }
        return false;
    }
};

题解

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size(), m = amount;
        vector<int> f(m + 1);

        f[0] = 1;
        for (int i = 0; i < n; i ++ )   // 枚举物品
            for (int j = coins[i]; j <= m; j ++ )   // 枚举背包容量
                f[j] += f[j - coins[i]];

        return f[m];
    }
};

题解

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size(), m = target;
        vector<int> f(m + 1);

        f[0] = 1;
        for (int i = 0; i <= m; i ++ )      // 枚举背包容量
            for (int j = 0; j < n; j ++ )   // 枚举物品
                if (i >= nums[j] && f[i] < INT_MAX - f[i - nums[j]])
                    f[i] += f[i - nums[j]];

        return f[m];
    }
};

题解

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    int n, k;

    void dfs(int start, int sum)
    {
        // 剪枝优化1
        if (path.size() + (9 - start + 1) < k)  return ;
        // 剪枝优化2
        if (sum > n)    return ;
        // 收集答案
        if (path.size() == k && sum == n)
        {
            res.push_back(path);
            return ;
        }

        for (int i = start; i <= 9; i ++ )
        {
            sum += i;
            path.push_back(i);

            dfs(i + 1, sum);

            sum -= i;
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum3(int _k, int _n) {
        k = _k, n = _n;
        dfs(1, 0);
        return res;
    }
};