//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {
	//当前考虑的元素
	while (l <= r && check()) {//区间[left,right]不符合题意
        //扩展左边界
    }
    //区间[left,right]符合题意，统计相关信息
}

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        // 枚举子数组的左边界
        for (int i = 0; i < n; i++) {
            int sum = 0;
            // 枚举子数组的右边界
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= s) {
                    ans = Math.min(ans, j - i + 1);
                    break;
                }
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        // 因为要找最小值，result设为 INT_MAX 最大值，方便后续比较
        int result = INT_MAX;
        int left = 0;
        int right = 0;
        int sum = 0;
        // 右指针右移，加入元素
        while (right <= n - 1) {
            sum += nums[right];
            // 可以不用判断左右指针相对位置，重合时，减完sum就为0了
            while (sum >= s) {
                result = min(right - left + 1, result);
                // 左指针右移，提前减去这个位置的元素
                sum -= nums[left];
                left++;
            }
            right++;
        }
        // 如果result没有被更新，说明没有符合条件的子数组
        return result == INT_MAX ? 0 : result;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        if (n <= 1) {
            return n;
        }
        int ans = 0;
        unordered_set<char> filter;
        int right = 0;
        for (int left = 0; left < n; left++) {
            // 左指针向右移动一格，移除掉遍历检查过的字符
            if (left != 0) {
                // 移除掉遍历检查过的字符
                filter.erase(s[left - 1]);
            }
            // 右指针向右移动，加入元素，直到遇到重复元素
            while (right <= n - 1 && !filter.count(s[right])) {
                filter.insert(s[right]);
                right++;
            }
            // 更新答案，此时右指针指向的元素是重复元素，所以 right - left 是当前窗口的长度
            ans = max(ans, right - left);
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int sSize = s.size();
        int pSize = p.size();

        if (sSize < pSize) {
            return {};
        }

        vector<int> result;

        // 承载s和p中每一个字符的数组，大小固定为26
        vector<int> sDict(26);
        vector<int> pDict(26);
        for (int i = 0; i < pSize; i++) {
            // 填入字母和字符a的差值作为存储判断的数据
            sDict[s[i] - 'a']++;
            pDict[p[i] - 'a']++;
        }
        // 至此，p字符串的结构体已经录入了pDict这个数组

        // 先比较一次s的开头字符串
        if (sDict == pDict) {
            result.emplace_back(0);
        }

        // 比较剩余的元素
        for (int i = 0; i < sSize - pSize; i++) {
            // 补上新的剩余字符计入
            sDict[s[pSize + i] - 'a']++;
            // 删掉之前计算的字符，保持窗口大小不变
            sDict[s[i] - 'a']--;

            if (sDict == pDict) {
                // i 是从减去p长度的后一个位置开始的，在s中的实际下标需要加 1
                result.emplace_back(i + 1);
            }
        }
        return result;
    }
};

class Solution {
public:
    vector<int> findSubstring(string& s, vector<string>& words) {
        vector<int> res; // 存储结果的向量，记录所有符合条件的起始索引
        
        // 获取关键参数：
        int m = words.size();     // words中单词的个数
        int n = words[0].size();  // 每个单词的长度（题目保证所有单词长度相同）
        int ls = s.size();        // 字符串s的长度
        
        // 外层循环：从0到n-1，处理不同的起始偏移量
        // 这样可以覆盖所有可能的对齐方式
        // 第二个结束条件就是剩余的字符串长度不足以支持分割
        for (int i = 0; i < n && i + m * n <= ls; ++i) {
            // 使用哈希表记录当前窗口内各单词出现次数与words中次数的差异
            unordered_map<string, int> differ;
            
            // 初始化滑动窗口：截取从位置i开始的m个单词
            for (int j = 0; j < m; ++j) {
                // 从s中截取一个单词并加入differ（增加计数）
                ++differ[s.substr(i + j * n, n)];
            }
            
            // 用words中的单词来平衡differ（减少计数）
            for (string& word : words) {
                // 如果某个单词在words中，就在differ中减少其计数
                if (--differ[word] == 0) {
                    // 如果计数减到0，就从differ中移除该单词
                    differ.erase(word);
                }
            }
            
            // 开始逐词滑动窗口遍历
            for (int start = i; start < ls - m * n + 1; start += n) {
                // 初始窗口第一次检查已完成，如果不是初始窗口，需要更新differ
                if (start != i) { 
                    // 添加新进入窗口的单词（窗口右边界新增的单词）
                    string word = s.substr(start + (m - 1) * n, n);
                    if (++differ[word] == 0) {
                        differ.erase(word); // 如果计数变为0，移除
                    }
                    
                    // 移除离开窗口的单词（窗口左边界移出的单词）  
                    word = s.substr(start - n, n);
                    if (--differ[word] == 0) {
                        differ.erase(word); // 如果计数变为0，移除
                    }
                }
                
                // 检查当前窗口是否匹配：如果differ为空，说明窗口内的单词与words完全匹配
                if (differ.empty()) {
                    res.emplace_back(start); // 记录当前起始位置
                }
            }
        }
        return res; // 返回所有找到的起始索引
    }
};

class Solution {
public:
    bool checkDict(unordered_map<char, int>& dyDict,
                   unordered_map<char, int>& tDict) {
        auto it = tDict.begin();
        while (it != tDict.end()) {
            if (it->second > dyDict[it->first]) {
                return false;
            }
            it++;
        }
        return true;
    }

    string minWindow(string s, string t) {
        int n = s.size();
        int m = t.size();
        if (n < m) {
            return "";
        }
        // 需要动态更新最小值
        string result = "";
        bool isFound = false;
        unordered_map<char, int> tDict;
        unordered_map<char, int> dynamicDitct;
        // 先填入即将用来比对hash表数据
        for (char c : t) {
            tDict[c]++;
        }
        // 思路，一路扩大检查的范围，直到包含的tDict中的字符数量后，再缩小范围到不包含，记录下区间大小
        int right = 0;
        int left = 0;
        while (right < n) {
            dynamicDitct[s[right]]++;
            // 包含了组成t的字符组合
            while (left < n && left + m <= right + 1 &&
                   checkDict(dynamicDitct, tDict)) {
                string temp = s.substr(left, right - left + 1);
                if (result == "") {
                    result = temp;
                } else {
                    result = result.size() > temp.size() ? temp : result;
                }
                dynamicDitct[s[left]]--;
                left++;
            }
            right++;
        }
        return result;
    }
};

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.empty() || t.empty() || s.length() < t.length()) return "";
        
        unordered_map<char, int> tCount;
        for (char c : t) tCount[c]++;
        
        int required = tCount.size(); // 需要匹配的字符种类数
        int formed = 0; // 当前已匹配的字符种类数
        
        unordered_map<char, int> windowCount;
        int left = 0, right = 0;
        int minLen = INT_MAX;
        int start = 0;
        
        while (right < s.length()) {
            char c = s[right];
            windowCount[c]++;
            
            // 检查当前字符是否达到t中的要求
            if (tCount.count(c) && windowCount[c] == tCount[c]) {
                formed++;
            }
            
            // 尝试收缩窗口
            while (left <= right && formed == required) {
                c = s[left];
                
                // 更新最小窗口
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }
                
                // 移动左指针
                windowCount[c]--;
                if (tCount.count(c) && windowCount[c] < tCount[c]) {
                    formed--;
                }
                left++;
            }
            
            right++;
        }
        
        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
};

class Solution {
public:
    unordered_map<char, int> ori, cnt;

    bool check() {
        for (const auto& p : ori) {
            if (cnt[p.first] < p.second) {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        for (const auto& c : t) {
            ++ori[c];
        }

        int l = 0, r = -1;
        int len = INT_MAX, ansL = -1, ansR = -1;

        while (r < int(s.size())) {
            if (ori.find(s[++r]) != ori.end()) {
                ++cnt[s[r]];
            }
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                }
                if (ori.find(s[l]) != ori.end()) {
                    --cnt[s[l]];
                }
                ++l;
            }
        }

        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};

class Solution {
public:
    bool isPalindrome(string s) {
        // 去除掉所有非字母数字的其他字符
        s.erase(remove_if(s.begin(), s.end(),
                          [](unsigned char c) { return !isalnum(c); }),
                s.end());
        // 转换为小写
        transform(s.begin(), s.end(), s.begin(), ::tolower);
        // 反转字符串
        string reversed = s;
        reverse(reversed.begin(), reversed.end());
        // 比较反转后的字符串是否与原字符串相同
        return reversed == s;
    }
};

class Solution {
public:
    bool isPalindrome(string s) {
        string sgood;
        for (char ch: s) {
            // 剔除非字母数字字符
            if (isalnum(ch)) {
                // 转换为小写并添加到新字符串
                sgood += tolower(ch);
            }
        }
        // 创建翻转的字符串也可以写作下面这样
        string sgood_rev(sgood.rbegin(), sgood.rend());
        return sgood == sgood_rev;
    }
};

class Solution {
public:
    bool isPalindrome(string s) {
        int n = s.size();
        int left = 0, right = n - 1;
        while (left < right) {
            while (left < right && !isalnum(s[left])) {
                ++left;
            }
            while (left < right && !isalnum(s[right])) {
                --right;
            }
            if (left < right) {
                if (tolower(s[left]) != tolower(s[right])) {
                    return false;
                }
                ++left;
                --right;
            }
        }
        return true;
    }
};

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size();
        if (n == 0) {
            return true;
        }
        int subPtr = 0;
        for (int i = 0; i < t.size(); i++) {
            // 有和子字符串相同的字符出现
            if (s[subPtr] == t[i]) {
                // 比较下一个
                subPtr++;
                // 子字符串遍历完成，结束
                if (subPtr == n) {
                    return true;
                }
            }
        }
        return false;
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        unordered_map<int, int> valueIndex;
        for (int i = 0; i < n; i++) {
            // 查看 hash 表中是否有和当前元素之和等于目标值的元素
            auto it = valueIndex.find(target - nums[i]);
            if (it != nullptr) {
                // 找到和为目标值的元素，返回这两个元素的下标
                return {it->second, i};
            }
            valueIndex[nums[i]] = i;
        }
        // 遍历完成，没有找到，返回空
        return {};
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        int left = 0;
        int right = n - 1;
        while (right > left) {
            if (numbers[left] + numbers[right] > target) {
                right--;
            } else if (numbers[left] + numbers[right] < target) {
                left++;
            } else {
                return {left + 1, right + 1};
            }
        }
        return {};
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for (int i = 0; i < numbers.size(); ++i) {
            int low = i + 1, high = numbers.size() - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (numbers[mid] == target - numbers[i]) {
                    return {i + 1, mid + 1};
                } else if (numbers[mid] > target - numbers[i]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }
        return {-1, -1};
    }
};

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int left = 0;
        int right = n - 1;
        int maxArea = 0;
        while (left < right) {
            // 计算当前面积，更新maxArea的值
            int areaHeight = min(height[left], height[right]);
            maxArea = max(maxArea, (right - left) * areaHeight);
            // 移动对应高度较短的那个指针
            height[left] >= height[right] ? right-- : left++;
        }
        return maxArea;
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        // 先排序
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        for (int i = 0; i < n - 2; i++) {
            int lock = nums[i];
            // 说明遍历到此处，后面的元素已经都大于0了
            if (lock > 0) {
                return result;
            }
            // 对第一个元素去重
            if (i > 0 && lock == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = lock + nums[left] + nums[right];
                if (sum > 0) {
                    // 结果大于0，缩小right指针
                    right--;
                } else if (sum < 0) {
                    // 结果小于0，增大left指针
                    left++;
                } else {
                    // 添加进结果数组中
                    result.push_back({nums[i], nums[left], nums[right]});
                    // 去重逻辑应该放在找到一个三元组之后，对left和right进行多移几位的操作
                    while (right > left && nums[right] == nums[right - 1])
                        right--;
                    while (right > left && nums[left] == nums[left + 1])
                        left++;
                    // 找到答案时，双指针同时收缩
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        if (n < 1) {
            return;
        }

        int slow = 0;
        for (int fast = 0; fast < n; fast++) {
            if (nums[fast] == 0) {
                continue;
            }
            nums[slow] = nums[fast];
            slow++;
        }
        for (int i = slow; i < n; i++) {
            nums[i] = 0;
        }
    }
};

#include <string>
using namespace std;

string s1;                // 空字符串
string s2 = "hello";      // 从C风格字符串构造
string s3(5, 'a');        // "aaaaa"
string s4(s2);            // 拷贝构造
string s5(s2, 1, 3);      // 从s2的第1位置开始取3个字符 -> "ell"

char c1 = s2[1];          // 'e'，不检查越界
char c2 = s2.at(1);       // 'e'，越界会抛出异常
int len = s2.length();    // 或 s2.size()，返回字符串长度
bool isEmpty = s2.empty();// 是否为空

// 无下标，用于拼接比较多
for (char c : s2) {
    cout << c;
}
// 或者下标遍历
for (int i = 0; i < s2.size(); ++i) {
    cout << s2[i];
}

s2.append(" world");     // s2变为"hello world"
// append可以追加字符串，不可以追加字符类型
// 追加字符可以使用push_back
s2.push_back('!');        // s2变为"hello world!"
// 也可以使用 += 追加字符或字符串
s2 += "!";
s2.insert(5, " ");       // 在第5位置插入空格 -> "hello world!"
s2.insert(s2.end(), s3.begin(), s3.end()); // 在s2末尾插入s3
s2.erase(5, 1);          // 从第5位置删除1个字符
s2.replace(0, 5, "hi");  // 将[0,5)替换为"hi" -> "hi world!"

// 翻转字符串的某个区间
void reverseString(string &s, int start, int end) {
    while (start < end) {
        swap(s[start++], s[end--]);
    }
}
// 使用库函数翻转
reverse(s2.begin(), s2.begin() + 5); // 翻转字符串的前5个字符 "hello world!" -> "olleH world!"

size_t pos = s2.find("world");  // 查找子串，返回起始索引，找不到返回 string::npos
if (pos != string::npos) {
    cout << "Found at: " << pos;
}

pos = s2.rfind("o");     // 从后往前查找
s2.replace(pos, 1, "a"); // 替换找到的字符

// 判断前缀/后缀
bool starts = s2.substr(0, 2) == "he"; // 手动判断前缀
bool startsWithHe = s2.compare(0, 2, "he") == 0; // 更标准但麻烦
// C++20起有 starts_with() 和 ends_with()

string sub = s2.substr(6, 5); // 从第6位置开始，取5个字符 -> "world"

// 转小写/大写一般要自己写循环或者使用<cctype>
for (char &c : s2) {
    c = tolower(c); // 需要 #include <cctype>
}

// 使用transform
transform(s2.begin(), s2.end(), s2.begin(), ::toupper); // 转大写

string line = "a b c";
stringstream ss(line);
string word;
while (ss >> word) {
    cout << word << endl;
}

int arr[5] = {1, 2, 3, 4, 5};
int arr2[] = {10, 20, 30}; // 自动推导大小

void reverseArray(int arr[], int start, int end) {
    while (start < end) {
        swap(arr[start++], arr[end--]);
    }
}

#include <vector>
using namespace std;

vector<int> v1;                // 空vector
vector<int> v2(5, 10);         // 5个元素，都是10
vector<int> v3 = {1, 2, 3};    // 列表初始化
vector<int> v4(v3);            // 拷贝构造
vector<int> v5(v3.begin(), v3.end()); // 用迭代器范围构造

int size = v1.size();     // 元素个数
bool isEmpty = v1.empty(); // 是否为空

int first = v3[0];        // 不检查边界
int second = v3.at(1);    // 检查边界，越界抛异常
int last = v3.back();     // 最后一个元素
int first2 = v3.front();  // 第一个元素

v1.push_back(100);       // 尾部插入
v1.pop_back();           // 尾部删除
v1.insert(v1.begin() + 1, 99); // 在第1位置后插入99
v1.erase(v1.begin());    // 删除第一个元素
v1.clear();              // 清空所有元素

// 下标遍历
for (int i = 0; i < v1.size(); ++i) {
    cout << v1[i];
}

// 迭代器遍历
for (auto it = v1.begin(); it != v1.end(); ++it) {
    cout << *it;
}

// 范围for遍历（推荐）
for (int x : v1) {
    cout << x;
}

#include <algorithm>
sort(v1.begin(), v1.end()); // 升序排序
sort(v1.begin(), v1.end(), greater<int>()); // 降序排序

auto it = find(v1.begin(), v1.end(), 3); // 返回迭代器
if (it != v1.end()) {
    cout << "Found: " << *it;
} else {
    cout << "Not found";
}

sort(v1.begin(), v1.end());
auto last = unique(v1.begin(), v1.end()); // 把重复的移到后面，返回新逻辑结尾
v1.erase(last, v1.end()); // 真正删除后面的重复元素

vector<vector<int>> matrix(3, vector<int>(4, 0)); // 3行4列，全0

#include <algorithm>

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size();
        if (n < 1)
            return n;
        int lenth = 1;
        int maxLenth = 1;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i + 1] > nums[i]) {
                lenth++;
                maxLenth = max(lenth, maxLenth);
            } else {
                lenth = 1;
            }
        }
        return maxLenth;
    }
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int n = nums.size();
        if (n < 1) {
            return n;
        }
        unordered_set<int> tempSet;
        for (int val : nums) {
            tempSet.insert(val);
        }
        int lenth = 1;
        int maxLenth = 1;
        for (const int& num : tempSet) {
            // 当前元素是前驱元素
            if (!tempSet.count(num - 1)) {
                int curretnNum = num;
                while (tempSet.count(curretnNum + 1)) {
                    lenth++;
                    curretnNum += 1;
                    maxLenth = max(maxLenth, lenth);
                }
            }
            // 非前驱元素了，重置lenth
            lenth = 1;
        }
        return maxLenth;
    }
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // 处理边界情况：数组为空或只有一个元素
        int max = 0, length = 0;
        if (nums.size() <= 1) {
            return nums.size() ? 1 : 0;  // 空数组返回0，单元素返回1
        }
        // 先对数组进行排序，将可能连续的数字放在一起
        std::sort(nums.begin(), nums.end());
        // 遍历排序后的数组，寻找连续序列
        for (int i = 0; i < nums.size() - 1; i++) {
            // 如果相邻元素差值为1，说明是连续序列
            if (nums[i + 1] - nums[i] == 1) {
                length++;  // 当前连续序列长度加1
            }
            // 如果相邻元素相等，跳过重复元素，继续检查下一个
            if (nums[i + 1] == nums[i]) {
                continue;
            }
            // 如果相邻元素差值不为1，说明连续序列中断
            if (nums[i + 1] - nums[i] != 1) {
                // 更新最大长度（length是间隔数，序列长度需要+1）
                if (length + 1 > max) {
                    max = length + 1;
                }
                length = 0;  // 重置当前序列长度
            }
        }
        // 检查最后一个连续序列（循环结束时可能还有未统计的序列）
        if (length + 1 > max) {
            max = length + 1;
        }
        // 返回最大长度，如果max为0说明没有连续序列，返回1（至少有一个元素）
        return max ? max : 1;
    }
};

int init = atexit([]()
{
    //力扣是从main开始进行计算的，这里先调用过ofstream让他初始化好，后面就不需要初始化了，结果会更快
    ofstream("display_runtime.txt") << "0";
});

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int idxm = m - 1;
        int idxn = n - 1;
        for (int i = m + n - 1; i >= 0; i--) {
            int currentm = idxm >= 0 ? nums1[idxm] : -INT_MAX;
            int currentn = idxn >= 0 ? nums2[idxn] : -INT_MAX;
            currentm > currentn ? idxm-- : idxn--;
            nums1[i] = max(currentm, currentn);
        }
    }
};

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int idxm = m - 1;
        int idxn = n - 1;
        
        for (int i = m + n - 1; i >= 0; i--) {
            if (idxm >= 0 && (idxn < 0 || nums1[idxm] > nums2[idxn])) {
                nums1[i] = nums1[idxm--];
            } else {
                nums1[i] = nums2[idxn--];
            }
        }
    }
};

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        
        // 如果nums2还有剩余元素
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
};

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];
        }
        sort(nums1.begin(), nums1.end());
    }
};

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
};

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != nums[left]) {
                left++;
                nums[left] = nums[right];
            }
        }
        // left 是下标，加1为长度
        return left + 1;
    }
};

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n <= 2) {
            return n;
        }
        int slow = 2, fast = 2;
        while (fast < n) {
            if (nums[slow - 2] != nums[fast]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> map;
        for (int i = 0; i < n; i++) {
            map[nums[i]]++;
        }
        for (auto it = map.begin(); it != map.end(); it++) {
            if (it->second > n / 2) {
                return it->first;
            }
        }
        return -1;
    }
};

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> map;
        for (int i = 0; i < n; i++) {
            map[nums[i]]++;
        }
        int max = 0;
        int maxItem = nums[0];
        for (auto it = map.cbegin(); it != map.cend(); it++) {
            if (it->second > max) {
                maxItem = it->first;
                max = it->second;
            }
        }
        return maxItem;
    }
};

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        return nums[n/2];
    }
};

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> temp(n);
        for (int i = 0; i < n; i++) {
            temp[(k + i) % n] = nums[i];
        }
        nums = temp;
    }
};

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();  // 获取数组的长度
        // 创建一个临时数组 temp，并将原数组 nums 的内容拷贝进去
        vector<int> temp = nums;
        // 关键步骤：将原数组 nums 再次拼接到 temp 后面
        // 这样就可以通过选取合适的起始位置，来得到旋转后的数组
        temp.insert(temp.end(), nums.begin(), nums.end());
        // 计算旋转的起始位置：
        // 我们想把原数组向右旋转 k 个位置。
        // 为了便于计算，我们令 start = n - k % n
        // 注意：k 可能大于 n，所以要取模：k % n
        int start = n - k % n; 
        // 这 n 个连续元素，就是原数组旋转 k 次后的正确顺序
        for (int i = 0; i < n; i++) {
            nums[i] = temp[start + i];
        }
    }
};

class Solution {
public:
    void reverse(vector<int>& nums, int left, int right) {
        while (left < right) {
            swap(nums[left], nums[right]);
            left++;
            right--;
        }
    }

    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

class Solution {
public:
    void rotate(string& str, int k) {
        int n = str.size();
        string temp = str + str;
        int start = n - k % n;
        str = temp.substr(start, n);
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int min = 10000;
        int maxProfit = 0;
        int n = prices.size();
        for (int i = 0; i < n; i++) {
            if (prices[i] < min) {
                min = prices[i];
            } else if (prices[i] - min > maxProfit) {
                maxProfit = prices[i] - min;
            }
        }
        return maxProfit;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxProfit = 0;
        int n = prices.size();
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }
};

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            // 判断当前位置 i 是否可达
            if (i <= rightmost) {
                // 更新最远可达位置
                rightmost = max(rightmost, i + nums[i]);
                // 如果最远可达位置大于等于最后一个下标，返回 true
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        // 如果遍历完成，最远可达位置还不到最后一个下标，返回 false
        return false;
    }
};

class Solution {
public:
    int jump(vector<int>& nums) {
        int maxPos = 0, n = nums.size(), end = 0, step = 0;
        for (int i = 0; i < n - 1; i++) {
            if (i <= maxPos) {
                maxPos = max(maxPos, i + nums[i]);
                if (end == i) {
                    end = maxPos;
                    step++;
                }
            }
        }
        return step;
    }
};

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size(), hIndex = 0;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (citations[i] <= citations[j] && citations[i] > count) {
                    count++;
                }
            }
            hIndex = max(hIndex, count);
        }
        return hIndex;
    }
};

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int hIndex = 0, i = citations.size() - 1;
        sort(citations.begin(), citations.end());
        while (i >= 0 && citations[i] > hIndex) {
            hIndex++;
            i--;
        }
        return hIndex;
    }
};

class RandomizedSet {
public:
    RandomizedSet() {
        srand((unsigned)time(NULL));
    }
    
    bool insert(int val) {
        if (indices.count(val)) {
            return false;
        }
        int index = nums.size();
        nums.emplace_back(val);
        indices[val] = index;
        return true;
    }
    
    bool remove(int val) {
        if (!indices.count(val)) {
            return false;
        }
        int index = indices[val];
        int last = nums.back();
        nums[index] = last;
        indices[last] = index;
        nums.pop_back();
        indices.erase(val);
        return true;
    }
    
    int getRandom() {
        // 测试用例保证调用此方法时集合中至少存在一个元素
        int randomIndex = rand()%nums.size();
        return nums[randomIndex];
    }
private:
    vector<int> nums;
    unordered_map<int, int> indices;
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> multiNums(n);
        vector<int> left(n, 0);
        vector<int> right(n, 0);

        left[0] = 1;
        for (int i = 1; i < n; i++) {
            // 此元素左侧所有乘积，为上一个left的总乘积，再乘以它左边的这个元素
            left[i] = left[i - 1] * nums[i - 1];
        }

        right[n - 1] = 1;
        for (int j = n - 2; j >= 0; j--) {
            // 元素右边乘积，为之前的总乘积数值，再乘以其右边元素
            right[j] = right[j + 1] * nums[j + 1];
        }

        for (int i = 0; i < n; i++) {
            multiNums[i] = left[i] * right[i];
        }

        return multiNums;
    }
};

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        vector<int> gasExt = {};
        gasExt.insert(gasExt.end(), gas.begin(), gas.end());
        gasExt.insert(gasExt.end(), gas.begin(), gas.end());
        vector<int> costExt = {};
        costExt.insert(costExt.end(), cost.begin(), cost.end());
        costExt.insert(costExt.end(), cost.begin(), cost.end());

        for (int i = 0; i < n; i++) {
            int gasRemain = 0;
            // 尝试从位置0出发，计算本轮的耗油量
            for (int j = i; j < n + i; j++) {
                gasRemain = gasRemain + gasExt[j] - costExt[j];
                // 中途不够了，开始下一轮
                if (gasRemain < 0) {
                    break;
                }
            }
            if (gasRemain < 0) {
                continue;
            }
            // 油量足够，返回这个索引
            if (gasRemain >= 0) {
                return i;
            }
        }
        return -1;
    }
};

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int i = 0;
        while (i < n) {
            int sumOfGas = 0, sumOfCost = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                if (sumOfCost > sumOfGas) {
                    break;
                }
                cnt++;
            }
            if (cnt == n) {
                return i;
            } else {
                i = i + cnt + 1;
            }
        }
        return -1;
    }
};