前端学数据结构与算法（十二）：有趣的算法 - 多指针与滑动窗口

给定两个数组，编写一个函数来计算它们的交集。

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays

解法1：

var intersection = function (nums1, nums2) {
  const set = new Set()
  nums1.forEach(num => {
    if (nums2.includes(num)) {
      set.add(num)
    }
  })
  return [...set]
};

解法2：

var intersection = function (nums1, nums2) {
  nums1.sort((a, b) => a - b)
  nums2.sort((a, b) => a - b)
  const set = new Set()
  nums1.forEach(num => {
    if (binarySearch(nums2, num)) {
      set.add(num)
    }
  })
  return [...set]
};

function binarySearch(arr, target) { // 二分查找
  let l = 0;
  let r = arr.length
  while (r > l) {
    const mid = l + (r - l) / 2 | 0
    if (arr[mid] === target) {
      return true
    } else if (arr[mid] > target) {
      r = mid
    } else {
      l = mid + 1
    }
  }
  return false
}

解法3：

var intersection = function (nums1, nums2) {
  nums1.sort((a, b) => a - b)
  nums2.sort((a, b) => a - b)
  let i = 0;
  let j = 0;
  const set = new Set()
  while (i < nums1.length && j < nums2.length) { //有一个到头结束循环
    if (nums1[i] === nums2[j]) { // 找到了交集
      set.add(nums1[i]) // 放入set内
      i++
      j++
    } else if (nums1[i] > nums2[j]) { // 谁数值小，+1 移动
      j++
    } else {
      i++
    }
  }
  return [...set]
};

给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted

var twoSum = function (numbers, target) {
  let l = 0 // 左指针
  let r = numbers.length - 1 // 右指针
  while (r > l) { // 不能 r >= l，因为不能使用同一个值两次
    if (numbers[r] + numbers[l] === target) {
      return [l + 1, r + 1]
    } else if (numbers[r] + numbers[l] > target) {
      r-- // 右指针向中间移动
    } else {
      l++ // 左指针向中间移动
    }
  }
  return []
};

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

示例：
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。
在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-wate

var maxArea = function (height) {
  let max = 0 // 保存最大的值
  let l = 0;
  let r = height.length - 1
  while (r > l) { // 不能相遇
    const h = Math.min(height[r], height[l])
    max = Math.max(h * (r - l), max) // 容量等于距离差 * 矮的那边条轴
    height[r] > height[l] ? l++ : r-- // 移动矮轴的指针
  }
  return max
};

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素a，b，c，使得a+b+c=0？
请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。

nums = [-1, 0, 1, 2, -1, -4]
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum

var threeSum = function (nums) {
  nums.sort((a, b) => a - b) // 排序
  const res = []
  for (let i = 0; i < nums.length; i++) {
    let l = i + 1
    let r = nums.length - 1
    if (nums[i] > 0) { // 如果第一个元素就大于0，后面也不用比了
      break;
    }
    if (i > 0 && nums[i] === nums[i - 1]) { // 跳过相同的数字
      continue
    }
    while (r > l) {
      const sum = nums[i] + nums[l] + nums[r];
      if (sum === 0) { // 正好找到
        res.push([nums[i], nums[l], nums[r]])
        while (r > l && nums[l] === nums[l + 1]) { // 跳过相同的数字，一个元素只用一次
          l++
        }
        while (r > l && nums[r] === nums[r - 1]) { // 跳过相同的数字，一个元素只用一次
          r--
        }
        r-- // 缩小范围
        l++ // 缩小范围
      } else if (sum > 0) {
        r-- // 右指针移动，减少下次计算的和
      } else { // sum < 0
        l++ // 左指针移动，增加下次计算的和
      }
    }
  }
  return res

};

给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

输入: [1,12,-5,-6,50,3], k = 4
输出: 12.75
解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

var findMaxAverage = function (nums, k) {
  let max = 0
  let sum = 0
  for (let i = 0; i < k; i++) {
    sum += nums[i] // 先求出第一个窗口
  }
  max = sum / k // 第一个窗口的平均值
  let j = k
  while (nums.length > j) {
    sum += nums[j] - nums[j - k] // 加上新元素，减去最左侧元素
    max = Math.max(sum / k, max) // 与之前窗口的平均值比较
    j++ // 向右滑动
  }
  return max // 返回最大窗口平均值
};

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence

var findLengthOfLCIS = function (nums) {
  let l = 0;
  let r = 0;
  let max = 0;
  while (nums.length > r) { // 只要窗口还在数组内活动
    if (r > 0 && nums[r - 1] >= nums[r]) { // 如果遇到的元素大于窗口最右侧值
      l = r // 重新统计长度
    }
    max = Math.max(max, r - l + 1) // 统计最长的长度
    r++ // 向右滑动
  }
  return max
};

给定一个含有n个正整数的数组和一个正整数s，找出该数组中满足其和≥s的长度最小的连续子数组，并返回其长度。
如果不存在符合条件的子数组，返回 0。

输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum

var minSubArrayLen = function (s, nums) {
  let l = 0
  let r = 0
  let sum = 0 // 窗口里的和
  let size = nums.length + 1 
  // 窗口的大小， 因为是要找到最小的窗口，所以设置一个比最大还 +1 的窗口
  // 如果能找到一个符合条件的子数组才会更新窗口的大小
  while (nums.length > l) { // 让左边界小于整个数组，为了遍历到每一个元素
    if (s > sum) {
      sum += nums[r++] // 窗口和小于s，移动右窗口
    } else {
      sum -= nums[l++] // 窗口大于s，移动左窗口
    }
    if (sum >= s) { // 找到符合的子数组
      size = Math.min(size, r - l) // 更新最小窗口的值
    }
  }
  return size === nums.length + 1 ? 0 : size
  // 如果size等于初始值，表示没有符合要求的子数组，否则有找到
};

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

var lengthOfLongestSubstring = function (s) {
  const set = new Set();
  let l = 0;
  let r = 0;
  let max = 0;
  while (l < s.length && r < s.length) {
    if (!set.has(s[r])) { // 如果查找表里没有
      set.add(s[r++]); // 添加右移窗口
    } else {
      set.delete(s[l++]); 
      // 从左侧开始删除，直到把新加入的且在查找表里有的元素删除为止
      // 然后窗口才会继续开始右滑
    }
    max = Math.max(max, r - l); // 更新最大的值
  }
  return max;
};