https://leetcode.cn/problems/minimum-swaps-to-group-all-1s-together-ii/
// 最少交换次数来组合所有的1 
// class Solution {
// public:
//     int minSwaps(vector<int>& nums) {
//         int k = 0;
//         for(auto e : nums)
//             if(e) k++;
        
//         int cnt_0 = 0;
//         int ret = INT_MAX;
//         int flag = 1;
//         for(int i = 0; i <= nums.size(); ++i)
//         {
//             if(flag && i == nums.size())
//             {
//                 i = (i+1) % nums.size();
//                 flag = 0;
//             }

//             if(i < k-1)
//             {
//                 if(nums[i] == 0)
//                     cnt_0 += 1;

//                 continue;
//             }

//             if(nums[i] == 0)
//                 cnt_0++;

//             ret = min(ret, cnt_0);
//             cout << cnt_0;

//             if(nums[i-k+1] == 0)
//                 cnt_0--;
//         }

//         return ret;
//     }
// };

// 1的个数就是窗口的大小
// 窗口中0的最小个数就是最小的交换次数

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int k = 0;
        for(auto e : nums)
            if(e) k++;

        if(k == 0)
            return 0;

        int cnt_0 = 0;
        int ret = INT_MAX;
        int left = 0;
        int right = 0;

        while(right < k)
        {
            if(nums[right] == 0)
                cnt_0 += 1;

            right++;
        }

        while(left < nums.size())
        {
            if(right == nums.size())  
                right = 0;

            ret = min(ret, cnt_0);
            if(nums[left] == 0)
            {
                cnt_0--;
            }
            
            left++;

            if(nums[right] == 0)
                cnt_0++;

            right++;
        }

        return ret;
    }
};
------------------------------------------------------------------------
https://leetcode.cn/problems/smallest-range-ii/
最小差值
class Solution {
public:
    int smallestRangeII(vector<int>& nums, int k) {
        // 0~i-1 变大 i~n-1变小
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int min_gap = nums.back()-nums[0];
        int max_num = 0;
        int min_num = INT_MAX;
        
        for(int i = 1; i < n; ++i)
        {
            max_num = max(nums[n-1]-k,nums[i-1]+k);
            min_num = min(nums[i]-k,nums[0]+k);
            min_gap = min(min_gap,max_num-min_num);
        }

        return min_gap;
    }
}; 
------------------------------------------------------------------------
https://leetcode.cn/problems/longest-substring-without-repeating-characters/
无重复字符的最长子串
//解题思路：滑动窗口(不回退的双指针)；利用flag数组充当窗口。
// class Solution {
// public:
//     int lengthOfLongestSubstring(string s) {
//         if(s.empty())
//             return 0;
//         int flag[256] = {0};
//         int ret_sum = 1;
//         int left = 0;
//         int right = 0;
//         while(right < s.size()){
//             if(flag[s[right]] == 0){
//                 flag[s[right]]++;
//             }else{
//                 while(left < right && s[left] != s[right]){
//                     flag[s[left]]--;
//                     left++;
//                 }       
//                 left++;
//             }

//             if(right-left+1 > ret_sum){
//                 ret_sum = right-left+1;
//             }
//             right++;           
//         }
//         return ret_sum;
//     }
// };


class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> counter;
        int left = 0;
        int right = 0;
        int ret = 0;
        while(right < s.size())
        {
            // 1.入窗口
            counter[s[right]]++; 
            // 2.判断          
            while(counter[s[right]] >= 2)
            {
                ret = max(ret,right-left);
                counter[s[left]]--;
                // if(counter[s[left]] == 0)
                // {
                //     counter.erase(s[left]);
                // }

                // 3.出窗口
                left++;
            }
            right++;
        }
        ret = max(ret,right-left);

        return ret;
    }
};