1. Solve the “puzzle” of strings

Anagrams: If two strings occur the same number of characters but in different order, they are anagrams

Tip: sliding window, check times

/ * * *@param {string} s
 * @param {string} p
 * @return {number[]}* /
var findAnagrams = function(s, p) {
  let map = {}, count = 0, ans = [];

  var resetMap = () = > {
      for (let key in map) {
          if(map.hasOwnProperty(key)) {
              map[key].count = map[key].originCount;
          }
      }
      count = 0;
  }

  for (let i = 0; i < p.length; i++) {
      if (map[p[i]]) {
          map[p[i]].count++;
          map[p[i]].originCount++;
      } else {
          map[p[i]] = {
              count: 1.originCount: 1}; }}let i = 0, j = 0;
  while (j < s.length) {
      if (map[s[j]] && map[s[j]].count > 0) {
          // The number of characters is -1 and the number of matches is +1
          map[s[j]].count--;
          count++;
          // The match is complete
          if (count == p.length) {
            ans.push(i);
            j++;
            while(s[i] == s[j]) {
                i++;
                ans.push(i);
                j++;
            }
            map[s[i]].count++;
            count--;
            i++;
          } else{ j++; }}else {
          if(! map[s[j]]) {// Not possible to start from j, window slide, start from scratch.
              j++;
              i = j;
              resetMap();
          } else {
              while(s[i] ! = s[j]) { map[s[i]].count++; count--; i++; } i++; j++; }}}return ans;
};
Copy the code
  1. The largest string containing at most K distinct characters

Solution: Maintain a sliding window of size K. When an element appears, and when an element does not appear, convergence is performed on the left side of the window and map is used to record the number of elements appearing

/ * * *@param {string} s
 * @param {number} k
 * @return {number}* /
var lengthOfLongestSubstringKDistinct = function(s, k) {
    if (k == 0) return 0;

    let map = {}, max = 0, count = 0;

    let i = 0, j = 0;
    // Slide window. Keep only K distinct characters in the window
    while (j < s.length) {
        //s[j] does not exist
        if(! map[s[j]]) {// Character count +1
            count++;
            map[s[j]] = 1;
            // If the window is larger than k, then the left side needs to converge until the window size becomes k again
            while (count > k) {
                map[s[i]]--;
                if (map[s[i]] == 0) { count--; } i++; }}else {
            // count +1
            map[s[j]]++;
        }
        max = Math.max(max, j - i + 1);
        j++;  
    }

    return max;
};
Copy the code
  1. The sum of the shortest length is k

Continuous sequences are considered sliding Windows

Left, right starts at 0, right sums to the right are less than k, right sums to the right are greater than k, left equals k, keep comparing lengths

/ * * *@param {number} target
 * @param {number[]} nums
 * @return {number}* /
var minSubArrayLen = function(target, nums) {
    var min = nums.length, left = 0, right = -1, sum = 0, flag = false;
    nums.forEach((num, index) = > {
        sum += num;
        right++;
        while(sum >= target) {
          flag = true;
          if (right - left + 1 < min) {
             min = right - left + 1; } sum -= nums[left]; left++; }});return flag ? min : 0;
};
Copy the code