class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (k<0) {
            return 0;
        }
        unordered_set<int> result;  //用集合避免重复
        unordered_map<int, int> hash;   //hash表来映射所需数值
        for (int i = 0; i<nums.size(); i++) {
            if (hash.count(nums[i]+k)) {
                result.insert(nums[i]+k);
            }
            if (hash.count(nums[i]-k)) {
                result.insert(nums[i]);
            }
            hash[nums[i]] += 1;
        }
        return result.size();
    }
};

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> sortNums = nums;
        sort(sortNums.begin(), sortNums.end());
        int str = 0,end = nums.size()-1;
        while (nums[str]==sortNums[str]) {
            if (str==end) {
                return 0;
            }
            str++;
        }
        while (nums[end]==sortNums[end]) {
            end--;
        }
        return end-str+1;
    }
};

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

第一种：3格的滑动窗口

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int str = 0 ,end = 2;
        int tol = 0;
        if (flowerbed.size()==1&&flowerbed[0]==0) {
            tol++;
        }else if(flowerbed[0]==0&&flowerbed[1]==0) {
            flowerbed[0]=1;
            tol++;
        }
        
        while (end<=flowerbed.size()-1) {
            if (!(flowerbed[str]||flowerbed[str+1]||flowerbed[end])) {
                flowerbed[str+1] = 1;
                tol++;
            }
            str++;
            end++;
        }
        if (flowerbed.size()>=3&&flowerbed[flowerbed.size()-1]==0&&flowerbed[flowerbed.size()-2]==0) {
            tol++;
        }
        return tol>=n?1:0;
    }
};

第二种：

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        for (int i = 0; i < flowerbed.size(); i++) {
            if (!flowerbed[i] && (i == 0 || !flowerbed[i - 1]) && (i == flowerbed.size() - 1 || !flowerbed[i + 1])) {
                flowerbed[i] = 1;
                n--;
            }
        }
        return n <= 0;
    }
};

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

判断数组中是否有重复的元素，并且下标之差不超过k。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        for (int i=0; i<nums.size(); i++) {
            if (hash.find(nums[i])!=hash.end()&&i-hash[nums[i]]<=k) {
                return 1;
            }else{
                hash[nums[i]] = i;
            }
        }
        return 0;
    }
};

解决方法：滑动窗口方案

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double r = INT_MIN;
        double sum = 0;
        for (int i = 0; i<nums.size(); i++) {
            if (i<k) {
                sum+=nums[i];
            }else{
                r = max(sum, r);
                sum +=nums[i]-nums[i-k];
            }
        }
        r = max(sum, r);
        return r/double(k);
    }
};

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>>result(numRows);
        for (int i = 0; i<numRows; i++) {
            result[i].resize(i+1);
            result[i][0] = result[i][i] = 1;
        
            for (int j = 1; j<i; j++) {
                result[i][j] = result[i-1][j-1]+result[i-1][j];
            }
        }
        return result;
        
     }
};