文章目录

• 长度最小子数组
• 无重复字符的最长子串
• [最大连续 1 的个数III](https://leetcode.cn/problems/max-consecutive-ones-iii/description/)
• 将x减到0的最小操作数

  长度最小子数组

  class Solution {
  public:
      int minSubArrayLen(int target, vector& nums) {
          int len = INT_MAX;
          int right = 0, left = 0;
          int sum = 0;
          while(left <= right && right < nums.size())
          {
              sum += nums[right++];//进窗口
              while(sum >= target) //判断
              {
                  len = min(len, right - left);
                  sum -= nums[left++]; // 出窗口
              }
          }
          return len == INT_MAX ? 0 : len;
      }
  };
  

  无重复字符的最长子串

  class Solution {
  public:
      int lengthOfLongestSubstring(string s) {
          int n = s.size();
          int left = 0, right = 0;
          int hash[127] = {0};
          int res = 0;
          while (right < n) {
              hash[s[right]]++; // 进窗口，右端滑动
              if (hash[s[right]] > 1) {
                  while (hash[s[left]] != hash[s[right]])
                      hash[s[left++]]--;
                  hash[s[left++]]--;
              } else {
                  res = max(res, right - left + 1);
              }
              right++;
          }
          return res;
      }
  };
  

  int max(int a, int b)
  {
      return a > b ? a : b;
  }
  int lengthOfLongestSubstring(char * s){
      int n = strlen(s);
      int left = 0, right = 0, res = 0;
      int hash[127] = {0};
      while(right < n)
      {
          hash[s[right]]++;
          while(hash[s[right]] > 1)
              hash[s[left++]]--;
          res = max(res,right - left + 1);
          right++;
      }
      return res;
  } 
  

  解析：

  ---

  最大连续 1 的个数III

  class Solution {
  public:
      int longestOnes(vector& nums, int k) {
          int res = 0,zero = 0;
          for(int left = 0,right = 0; right < nums.size();right++)
          {
              if(nums[right] == 0)    zero++;//进窗口
              while(zero > k)
              {
                  if(nums[left++] == 0) zero--;
              }    
              res = max(res,right - left + 1);
          }
          return res;
      }
  };
  

  class Solution {
  public:
      int longestOnes(vector& nums, int k) {
          int left = 0, right = 0;
          int zero = 0, res = 0;
          while (right < nums.size()) {
              // 进窗口
              while (right < nums.size() && nums[right])
                  right++;
              // 判断
              if (right < nums.size() && ++zero <= k) {
                  right++;
                  // 数据更新
                  res = max(res, right - left);
              } else {
                  // 数据更新
                  res = max(res, right - left);
                  // 出窗口
                  while (left < right && nums[left])
                      left++;
                  k--;
                  left++;
                  right++;
              }
          }
          return res;
      }
  };
  

  将x减到0的最小操作数

  正难则反

  该题从正面去解，一会儿左一会儿右全凭场景所变化，编码写起来非常繁琐；此时，运用数学思维反证法来解决会不会简单些呢？该题需要求最小操作数，那也就意味着剩下的数据量是最大的，而且因为每次操作都在最左或者最右边，那也就是说剩下的数据是原数据的连续子串;OK，现在我们只需要求出一个符合的尽可能保证数据量大且其sum值等于sum(nums) - x 的连续子串即可.

  那现在将符合要求数据看成一个窗口往后滑动即可。

  class Solution {
  public:
      int minOperations(vector& nums, int x) {
          int sum = 0;
          for(int e : nums)   sum += e;
          if(x > sum) return -1;
          if(x == sum) return nums.size();
          int target = sum - x;
          int res = -1;
          for(int left = 0, right = 0, tmp = 0; right < nums.size(); right++)
          {
              tmp += nums[right];//进窗口
              while(tmp >= target)
              {
                  if(tmp == target)   res = max(res, right - left +1);//判断+记录长度
                  tmp -= nums[left++];// 出窗口
              }
          }
          if(res == -1)
              return res;
          return nums.size() - res;
      }
  };
  

  class Solution {
  public:
      int minOperations(vector& nums, int x) {
          int sum = 0;
          for (int e : nums)
              sum += e;
          if (x > sum)
              return -1;//细节
          int target = sum - x;
          int res = -1;
          for (int left = 0, right = 0, tmp = 0; right < nums.size(); right++) {
              tmp += nums[right]; // 进窗口
              while (tmp > target) // 判断
                  tmp -= nums[left++]; // 出窗口
              if (tmp == target)
                  res = max(res, right - left + 1); // 更新数据
          }
          if (res == -1)
              return res;
          return nums.size() - res;
      }
  };