滑动窗口

发表于 | 分类于 | | 阅读次数:

滑动窗口模式用在给定数组或链表的特定窗口大小上执行所需的操作

一般的解法是从第一个元素开始滑动窗口，维持一前一后两个游标，根据所求解的问题调整窗口长度

leetcode 53
描述： Given an integer array nums,find the contiguous subarray (containing at least one number ， which has the largest sum and return its sum.
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
  let sum = 0,
    max = nums[0],
    size = nums.length;
  for (let i = 0; i < size; i++) {
    sum += nums[i];
    max = max > sum ? max : (max = sum);
    if (sum < 0) {
      sum = 0;
    }
  }
  return max;
};

leetcode 3
描述：Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  const size = s.length,
    f1 = s.charAt(0),
    tmpArr = [f1];
  if (size === 0) return 0;
  if (size === 1) return 1;
  let max = 0;
  for (let i = 1; i < size; i++) {
    let c = s.charAt(i),
      existed_pos = tmpArr.indexOf(c);
    if (existed_pos > -1) {
      if (i === size - 1) break;
      max = max > tmpArr.length ? max : (max = tmpArr.length);
      i = i - (tmpArr.length - existed_pos - 1);
      c = s.charAt(i);
      tmpArr.length = 0;
    }
    tmpArr.push(c);
  }
  max = max > tmpArr.length ? max : (max = tmpArr.length);
  return max;
};