class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (k < 0) return 0;
        map<int, int> m;
        for (int x : nums) {
            m[x]++;
        }
        int ans = 0;
        auto ite = m.begin();
        while (ite != m.end()) {
            if (k) {
                int sum = ite->first + k;
                if (m.count(sum)) ans++;//这里要用count函数查询是否存在元素，直接访问会超时
            } else {
                if (ite->second > 1) ans++;
            }
            ite++;
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        map<int, int> v,n;
        vector<int> ans;
        for (int x : nums1) {
            v[x]++;
        }
        for (int x : nums2) {
            n[x]++;
        }
        sort(nums1.begin(), nums1.end());
        nums1.erase(unique(nums1.begin(), nums1.end()), nums1.end());
        for (int x : nums1) {
            if (v[x] && n[x]) {
                int l = v[x] > n[x] ? n[x] : v[x];
                for (int i = 0; i < l; i++)
                ans.push_back(x);
            }
        }
        return ans;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* dummy = new ListNode(0), *a, *b, *c;
        dummy->next = head;
        a = b = c = dummy;
        for (int i = 0; i < m - 1; i++) {
            a = a->next;
            b = b->next;
        }
        for (int i = 0; i < n - m + 1; i++) {
            b = b->next;
        }
        c = b->next;
        b->next = NULL;
        a->next = reverseList(a->next);
        while (a->next != NULL) {
            a = a->next;
        }
        a->next = c;
        return dummy->next;
    }
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode *temp = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return temp;
    }
};

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> cpy(nums.begin(), nums.end());
        sort(cpy.begin(), cpy.end());
        int len = nums.size();
        int j = len - 1, i = 0;
        for ( ; j >= 0; j--) {
            if (nums[j] != cpy[j]) {
                break;
            }
        }
        for (; i < len; i++) {
            if (nums[i] != cpy[i]) {
                break;
            }
        }
        int ans = j - i + 1;
        return ans > 0 ? ans : 0;
    }
};