合并两个有序数组

合并两个有序数组

题目地址 (opens new window)

// 正向双指针，每次从两个数组头部取出比较小的数字放到结果中
var merge = function(nums1, m, nums2, n) {
  let p1 = 0,
    p2 = 0;
  const sorted = new Array(m + n).fill(0);
  let cur;
  while (p1 < m || p2 < n) {
    if (p1 === m) {
      cur = nums2[p2++];
    } else if (p2 === n) {
      cur = nums1[p1++];
    } else if (nums1[p1] < nums2[p2]) {
      cur = nums1[p1++];
    } else {
      cur = nums2[p2++];
    }
    sorted[p1 + p2 - 1] = cur;
  }
  for (let i = 0; i < m + n; i++) {
    nums1[i] = sorted[i];
  }
};

// 逆向双指针，指针从后向前遍历，每次取两者间较大值放在 nums1 后面
var merge = function(nums1, m, nums2, n) {
  let p1 = m - 1,
    p2 = n - 1;
  let tail = m + n - 1;
  let cur;
  while (p1 >= 0 || p2 >= 0) {
    if (p1 === -1) {
      cur = nums2[p2--];
    } else if (p2 === -1) {
      cur = nums1[p1--];
    } else if (nums1[p1] > nums2[p2]) {
      cur = nums1[p1--];
    } else {
      cur = nums2[p2--];
    }
    nums1[tail--] = cur;
  }
};

有序数组的平方

题目地址 (opens new window)

var sortedSquares = function(nums) {
  let i = 0,
    j = nums.length - 1,
    k = nums.length - 1,
    res = [];
  while (k >= 0) {
    const left = nums[i] ** 2,
      right = nums[j] ** 2;
    if (left < right) {
      res[k] = right;
      j--;
    } else {
      res[k] = left;
      i++;
    }
    k--;
  }
  return res;
};

颜色分类

题目地址 (opens new window)

var sortColors = function(nums) {
  let left = 0,
    right = nums.length - 1,
    cur = 0;
  while (cur <= right) {
    if (nums[cur] === 0) {
      // 0 往前放
      [nums[left], nums[cur]] = [nums[cur], nums[left]];
      left++;
      cur++;
    } else if (nums[cur] === 1) {
      // 1 在原位置不动
      cur++;
    } else if (nums[cur] === 2) {
      // 2 往后放
      [nums[cur], nums[right]] = [nums[right], nums[cur]];
      right--;
    }
  }
};

验证回文串

题目地址 (opens new window)

var isPalindrome = function(s) {
  s = s.replace(/[^a-zA-Z0-9]/g, "").toLowerCase();
  let l = 0,
    r = s.length - 1;
  while (l < r) {
    if (s[l] !== s[r]) {
      return false;
    }
    l++;
    r--;
  }
  return true;
};

回文子串

题目地址 (opens new window)

// 枚举出所有的子串，然后再判断这些子串是否是回文
var countSubstrings = function(s) {
  let res = 0;
  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j <= s.length; j++) {
      if (isPalindrome(s.substring(i, j))) res++;
    }
  }
  return res;
};

function isPalindrome(s) {
  let i = 0,
    j = s.length - 1;
  while (i < j) {
    if (s[i] !== s[j]) return false;
    i++;
    j--;
  }
  return true;
}

// 枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展
var countSubstrings = function(s) {
  let res = 0;
  for (let i = 0; i < s.length; i++) {
    res += countPalindrome(s, i, i);
    res += countPalindrome(s, i, i + 1);
  }
  return res;
};

function countPalindrome(s, i, j) {
  let num = 0;
  while (i >= 0 && j < s.length && s[i] === s[j]) {
    num++;
    i--;
    j++;
  }
  return num;
}

最长回文子串

题目地址 (opens new window)

// 中心扩展
var longestPalindrome = function(s) {
  const n = s.length;
  if (n < 2) {
    return s;
  }
  let res = "";
  for (let i = 0; i < n; i++) {
    // 回文子串长度是奇数
    helper(i, i);
    // 回文子串长度是偶数
    helper(i, i + 1);
  }

  function helper(l, r) {
    while (l >= 0 && r < n && s[l] === s[r]) {
      l--;
      r++;
    }
    // 此时 l 到 r 的距离为 r-l+1，但是 l，r 两个边界不能取，所以应该取 l+1 到 r-1 的区间，长度为 (r-1)-(l+1)+1 = r-l-1
    if (r - l - 1 > res.length) {
      // 取 [l+1, r-1] 这个区间的长度
      res = s.slice(l + 1, r);
    }
  }

  return res;
};

三数之和

题目地址 (opens new window)

方法一：两层循环 + set。时间复杂度为：O(n^2)，空间复杂度为：O(n)。

方法二：排序 + 双指针。时间复杂度为：O(n^2)，空间复杂度为：O(1)。

var threeSum = function(nums) {
  const len = nums.length;
  const res = [];

  nums.sort((a, b) => a - b);
  for (let i = 0; i < len; i++) {
    if (nums[i] > 0) break; // 如果当前数字大于 0，那么三数之和一定大于 0，结束循环
    if (i > 0 && nums[i - 1] === nums[i]) continue; // 去重
    let l = i + 1,
      r = len - 1; // l、r 分别指向 i 后面元素的两端
    while (l < r) {
      const sum = nums[i] + nums[l] + nums[r];
      if (sum === 0) {
        res.push([nums[i], nums[l], nums[r]]);
        while (nums[l] === nums[l + 1]) l++; // 去重
        while (nums[r] === nums[r - 1]) r--; // 去重
        l++;
        r--;
      } else if (sum < 0) {
        l++;
      } else {
        r--;
      }
    }
  }

  return res;
};

盛最多水的容器

题目地址 (opens new window)

var maxArea = function(height) {
  let l = 0,
    r = height.length - 1,
    res = 0;

  while (l < r) {
    // 每次移动较小的指针
    if (height[l] < height[r]) {
      res = Math.max(res, (r - l) * height[l]);
      l++;
    } else {
      res = Math.max(res, (r - l) * height[r]);
      r--;
    }
  }

  return res;
};

长度最小的子数组

题目地址 (opens new window)

var minSubArrayLen = function(target, nums) {
  const len = nums.length;
  let left = 0,
    sum = 0,
    res = len + 1;
  for (let right = 0; right < len; right++) {
    sum += nums[right];
    while (sum >= target) {
      res = Math.min(res, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }
  return res > len ? 0 : res;
};

无重复字符的最长子串 ✅

题目地址 (opens new window)

// 时间和空间复杂度都是 O(n)
var lengthOfLongestSubstring = function(s) {
  const set = new Set(); // 存储窗口内的字符
  let i = 0, // 窗口左边界
    j = 0, // 窗口右边界
    max = 0;
  while (j < s.length) {
    if (!set.has(s[j])) {
      set.add(s[j++]); // 把新字符加入窗口，j 右移
      max = Math.max(max, set.size); // 更新最大长度
    } else {
      set.delete(s[i++]); // 删除窗口最左边的字符，i 右移
    }
  }
  return max;
};

最小覆盖子串 ✅

题目地址 (opens new window)

// 时间复杂度是 O(m+n)，m 是 s 的长度，n 是 t 的长度
// 空间复杂度是 O(k)，k 是 t 中不同字符的种类数
var minWindow = function(s, t) {
  const obj = {}; // 记录窗口内每个字符数量相对于 t 需求的"差值"
  for (const c of t) {
    obj[c] = obj[c] ? obj[c] + 1 : 1;
  }
  let left = 0, // 在满足条件后，收缩窗口，找最小长度
    right = 0; // 扩张窗口，直到包含 t 的所有字符
  let count = Object.keys(obj).length; // t 中不同字符的种类数
  let minLen = Infinity,
    minStart = 0; // 最小子串的长度和起始位置
  while (right < s.length) {
    const c = s[right++];
    if (obj[c] !== undefined) {
      obj[c]--; // 消耗一个需求
      if (obj[c] === 0) {
        count--; // 这个字符已经 "凑够了"
      }
    }
    while (count === 0) {
      // 1. 先记录当前窗口（收缩前）
      if (right - left < minLen) {
        minLen = right - left;
        minStart = left;
      }
      // 2. 弹出左边字符，尝试收缩
      const c = s[left++];
      if (obj[c] !== undefined) {
        obj[c]++; // 还回去这个需求
        if (obj[c] > 0) {
          count++; // 又出现缺口了，停止收缩
        }
      }
    }
  }
  return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
};

替换后的最长重复字符

题目地址 (opens new window)

枚举字符串中的每一个位置作为右端点，然后找到其最远的左端点的位置，满足该区间内除了出现次数最多的那一类字符之外，剩余的字符（即非最长重复字符）数量不超过 k 个。

使用双指针维护这些区间，每次右指针右移，如果区间仍然满足条件，那么左指针不移动，否则左指针至多右移一格，保证区间长度不减小。

虽然这样的操作会导致部分区间不符合条件，即该区间内非最长重复字符超过了 k 个。但是这样的区间也同样不可能对答案产生贡献。当我们右指针移动到尽头，左右指针对应的区间的长度必然对应一个长度最大的符合条件的区间。

由于字符串中仅包含大写字母，我们可以使用一个长度为 26 的数组维护每一个字符的出现次数。每次区间右移，我们更新右移位置的字符出现的次数，然后尝试用它更新重复字符出现次数的历史最大值，最后我们使用该最大值计算出区间内非最长重复字符的数量，以此判断左指针是否需要右移即可。

var characterReplacement = function(s, k) {
  const n = s.length;
  const arr = new Array(26).fill(0);
  const baseCharCode = "A".charCodeAt();
  let max = 0, // 区间内出现次数最多的字符的最大次数
    left = 0,
    right = 0;

  while (right < n) {
    arr[s[right].charCodeAt() - baseCharCode]++;
    max = Math.max(max, arr[s[right].charCodeAt() - baseCharCode]);
    if (right - left + 1 - max > k) {
      // 除了出现次数最多的字符之外，剩余的字符数量如果超过 k 个，就需要移动左指针
      arr[s[left].charCodeAt() - baseCharCode]--;
      left++;
    }
    right++;
  }

  return right - left;
};

找到字符串中所有字母异位词

题目地址 (opens new window)

因为字符串 p 的异位词的长度一定与字符串 p 的长度相同，所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。

var findAnagrams = function(s, p) {
  const sLen = s.length,
    pLen = p.length;

  if (sLen < pLen) {
    return [];
  }

  const res = [];
  const sCount = new Array(26).fill(0);
  const pCount = new Array(26).fill(0);
  const baseCharCode = "a".charCodeAt();

  for (let i = 0; i < pLen; i++) {
    sCount[s[i].charCodeAt() - baseCharCode]++;
    pCount[p[i].charCodeAt() - baseCharCode]++;
  }

  if (sCount.toString() === pCount.toString()) {
    res.push(0);
  }

  for (let i = 0; i < sLen - pLen; i++) {
    // 移动窗口，注意保持窗口大小不变
    sCount[s[i].charCodeAt() - baseCharCode]--;
    sCount[s[i + pLen].charCodeAt() - baseCharCode]++;

    if (sCount.toString() === pCount.toString()) {
      res.push(i + 1);
    }
  }

  return res;
};