LC T 100 #

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  const map = new Map()
  for (let i = 0; i < nums.length; i++) {
    const gap = target - nums[i]
    if (map.has(nums[i])) {
      return [map.get(nums[i]), i]
    }
    map.set(gap, i)
  }
  return []
}

var groupAnagrams = function (strs) {
  var map = new Map()
  for (var i = 0; i < strs.length; i++) {
    var str = strs[i]
    // 排序好的字符串作为key
    var sortStr = Array.from(str).sort().join('')
    if (map.has(sortStr)) {
      map.get(sortStr).push(str)
    } else {
      map.set(sortStr, [str])
    }
  }
  // map.values()返回迭代器，需要转换为数组
  return Array.from(map.values())
}

// 方法一：排序遍历
var longestConsecutive = function (nums) {
  if (nums.length === 0) {
    return 0
  }
  // 先给数组排序
  nums.sort((a, b) => a - b)
  var count = 1
  var max = 1
  for (var i = 0; i < nums.length; i++) {
    var cur = nums[i]
    var next = nums[i + 1]
    // 相同元素跳过
    if (cur === next) {
      continue
    }
    // 下一个元素比当前元素大1，则计数器加1
    if (cur + 1 === next) {
      count += 1
    } else {
      // 重置计数器
      count = 1
    }
    // 更新最大值
    max = Math.max(count, max)
  }
  return max
}

// 方法二：哈希表
var longestConsecutive = function(nums) {
  var res = 0;
  var set = new Set(nums); // 把 nums 转成哈希集合
  for (var x of set) { // 遍历哈希集合
    if (set.has(x - 1)) {
      continue;
    }
    // x 是序列的起点
    var y = x + 1;
    while (set.has(y)) { // 不断查找下一个数是否在哈希集合中
      y++;
    }
    // 循环结束后，y-1 是最后一个在哈希集合中的数
    // 从 x 到 y-1 一共 y-x 个数
    res = Math.max(res, y - x); 
  }
  return res;
};

// 如果数组没有0，那么快慢指针始终指向同一个位置，每个位置自己和自己交换
// 如果数组有0，快指针先走一步，此时慢指针对应的就是0，所以要交换
var moveZeroes = function (nums) {
  var slow = 0, fast = 0;
  while (fast < nums.length) {
    if (nums[fast] !== 0) {
      var tmp = nums[slow];
      nums[slow] = nums[fast];
      nums[fast] = tmp;
      slow += 1;
    }
    fast += 1;
  }
}

var maxArea = function (height) {
  var head = 0, tail = height.length - 1;
  var max = 0;
  while (head !== tail) {
    var h = Math.min(height[head], height[tail]);
    var long = tail - head;
    max = Math.max(max, h * long);

    if (height[head] < height[tail]) head += 1;
    else tail -= 1;
  }
  return max;
}

var threeSum = function (nums) {
  // 先按升序排序
  nums.sort((a, b) => a - b);
  var res = [];
  for (var k = 0;k < nums.length - 2;k++) {
    // 如果最小的元素都大于0，直接break，后面的都大于0
    if (nums[k] > 0) break;
    // 跳过相同的元素组合
    if (k > 0 && nums[k] === nums[k - 1]) continue;
    var i = k + 1, j = nums.length - 1;
    while (i < j) {
      var sum = nums[k] + nums[i] + nums[j];
      if (sum === 0) {
        // 记录组合
        res.push([nums[k], nums[i], nums[j]]);
        // i和j向内移动，并跳过重复的值，防止记录了重复的结果
        while (i < j && nums[i] === nums[++i]);
        while (i < j && nums[j] === nums[--j]);
      } else if (sum < 0) {
        // sum小于0，说明偏小，需要i向内移动，来增大sum
        while (i < j && nums[i] === nums[++i]);
      } else {
        // sum大于0，说明偏大，需要j向内移动，来减小sum
        while (i < j && nums[j] === nums[--j]);
      }
    }
  }
  return res;
}

// 方法一：用数组存储前缀和后缀最大值
var trap = function (height) {
  var len = height.length;
  // 计算出前缀最大值，用数组存储
  var preMax = new Array(len);
  preMax[0] = height[0];
  for (var i = 1;i < len;i++) {
    preMax[i] = Math.max(preMax[i - 1], height[i]);
  }

  // 计算后缀最大值，用数组存储
  var sufMax = new Array(len);
  sufMax[len - 1] = height[len - 1];
  for (var j = len - 2;j > -1;j--) {
    sufMax[j] = Math.max(sufMax[j + 1], height[j]);
  }

  // 每个位置能接的水的数量，为当前位置的前缀和后缀最大值的较小者，减去当前位置的值
  var res = 0;
  for (var k = 0;k < len;k++) {
    res += Math.min(preMax[k], sufMax[k]) - height[k];
  }
  return res;
}

// 方法二：用头尾双指针优化
var trap = function (height) {
  var left = 0, right = height.length - 1;
  var leftMax = 0, rightMax = 0;
  var res = 0;
  while (left < right) {
    leftMax = Math.max(leftMax, height[left]);
    rightMax = Math.max(rightMax, height[right]);
    if (leftMax < rightMax) {
      res += leftMax - height[left];
      left += 1;
    } else {
      res += rightMax - height[right];
      right -= 1;
    }
  }
  return res;
}

var lengthOfLongestSubstring = function (s) {
  // map记录每个字符以及目前为止最后一次出现的位置
  var map = new Map();
  // 注意左指针从 -1 开始
  var left = -1;
  var res = 0;
  for (var right = 0;right < s.length;right++) {
    var ch = s[right];
    if (map.has(ch)) {
      // 更新左指针
      left = Math.max(left, map.get(ch));
    }
    // 记录当前字符以及索引
    map.set(ch, right);
    // 更新最大长度
    res = Math.max(res, right - left);
  }
  return res;
}

// 代码纯享版
var findAnagrams = function (s, p) {
  var res = [];
  var arrP = new Array(26).fill(0);
  var arrS = new Array(26).fill(0);

  for (var c of p) {
    arrP[c.charCodeAt() - 'a'.charCodeAt()] += 1;
  }

  for (var right = 0;right < s.length;right++) {
    arrS[s[right].charCodeAt() - 'a'.charCodeAt()] += 1;
    var left = right - p.length + 1;
    if (left < 0) {
      continue;
    }
    if (arrP.join('') === arrS.join('')) {
      res.push(left);
    }
    arrS[s[left].charCodeAt() - 'a'.charCodeAt()] -= 1;
  }
  return res;
}

// 数组弄长一点，代码简洁一点
var findAnagrams = function(s, p) {
  var len = s.length;
  // 'z' 的 charCodeAt() 为 122，其实123就可以了，128好看点
  var arrS = new Array(128).fill(0);
  var arrP = new Array(128).fill(0);
  for (var ch of p) {
    arrP[ch.charCodeAt()] += 1;
  }
  var res = [];
  for (var right = 0; right < len; right++) {
    arrS[s[right].charCodeAt()] += 1;
    var left = right - p.length + 1;
    if (left < 0) {
      continue;
    }
    if (arrS.toString() === arrP.toString()) {
      res.push(left);
    }
    arrS[s[left].charCodeAt()] -= 1;
  }
  return res;
}

// 详细注释版
var findAnagrams = function (s, p) {
  var res = [];
  // 统计 p 每种字母出现次数
  var arrP = new Array(26).fill(0);
  // 统计 s 长为 len(p) 的子串 s' 每种字母的出现次数
  var arrS = new Array(26).fill(0);
  for (var c of p) {
    // charCodeAt() 返回字符的 Unicode 编码值，'a' 的 charCodeAt() 为 97
    arrP[c.charCodeAt() - 'a'.charCodeAt()] += 1;
  }

  for (var right = 0; right < s.length; right++) {
    // 开始记录子串 s' 每种字母的出现次数
    // 右端点字母进入窗口
    arrS[s[right].charCodeAt() - 'a'.charCodeAt()] += 1;
    const left = right - p.length + 1;
    // 窗口长度不足 len(p)
    if (left < 0) {
      continue;
    }
    // s' 和 p 的每种字母的出现次数都相同
    if (arrP.join('') === arrS.join('')) {
      // 记录子串的起始索引位置
      res.push(left);
    }
    // 左端点字母离开窗口
    arrS[s[left].charCodeAt() - 'a'.charCodeAt()] -= 1;
  }
  return res;
};

// 方法一：双重遍历，时间复杂度O(n^2)
var subarraySum = function (nums, k) {
  var count = 0;
  for (var i = 0;i < nums.length;i++) {
    var sum = 0;
    for (var j = i;j < nums.length;j++) {
      sum += nums[j];
      if (sum === k) {
        count += 1;
      }
    }
  }
  return count;
}

// 方法二：前缀和 + 哈希表，时间复杂度O(n)
var subarraySum = function (nums, k) {
  var map = new Map();
  map.set(0, 1);
  var prefix = 0;
  var count = 0;
  for (var num of nums) {
    prefix += num;
    if (map.has(prefix - k)) {
      count += map.get(prefix - k);
    }
    if (map.has(prefix)) {
      map.set(prefix, map.get(prefix) + 1);
    } else {
      map.set(prefix, 1);
    }
  }
  return count;
}

// 使用普通对象代码会更加简洁,但效率没有map高
var subarraySum = function (nums, k) {
  var obj = { 0: 1 };
  var prefix = 0;
  var count = 0;
  for (var num of nums) {
    prefix += num;
    if (obj[prefix - k]) {
      count += obj[prefix - k];
    }
    if (obj[prefix]) {
      obj[prefix] += 1;
    } else {
      obj[prefix] = 1;
    }
  }
  return count;
}

var maxSlidingWindow = function (nums, k) {
  if (nums.length === 0 || k === 0) {
    return [];
  }
  var deque = [];
  var res = [];
  // i、j 分别表示滑动窗口的左右边界
  for (var i = 1 - k, j = 0; j < nums.length; i++, j++) {
    // 滑动窗口往右移动时，首先删除队列中不存在于窗口中的元素
    if (i > 0 && deque[0] === nums[i - 1]) {
      deque.shift();
    }

    // 保证队列的单调递减，将队列中所有小于当前元素的元素删除
    while (deque.length > 0 && deque[deque.length - 1] < nums[j]) {
      deque.pop();
    }

    // 将当前元素加入队列
    deque.push(nums[j]);
    // 当滑动窗口的宽度为 k 时，将当前窗口的最大值加入结果数组
    // deque是单调递减队列，第一个元素是最大的
    if (i >= 0) {
      res.push(deque[0]);
    }
  }
  return res;
}

var isCovered = function (arrS, arrT) {
  // 一定要注意是小于等于 ≤ ！
  for (var i = 'A'.charCodeAt(); i <= 'Z'.charCodeAt(); i++) {
    if (arrS[i] < arrT[i]) {
      return false;
    }
  }
  for (var j = 'a'.charCodeAt(); j <= 'z'.charCodeAt(); j++) {
    if (arrS[j] < arrT[j]) {
      return false;
    }
  }
  return true;
}

var minWindow = function (s, t) {
  var len = s.length;
  // 'z'的charCodeAt()为122，所以其实长度123就够用了
  var arrS = new Array(128).fill(0);
  var arrT = new Array(128).fill(0);
  // 记录t中每个字符的出现次数
  for (var ch of t) {
    arrT[ch.charCodeAt()] += 1;
  }

  var ansLeft = -1, ansRight = len;
  var left = 0;
  for (var right = 0; right < len; right++) {
    // 右端点字母进入窗口
    arrS[s[right].charCodeAt()] += 1;
    while (isCovered(arrS, arrT)) {
      // 如果找到更短的子串，则更新ansLeft和ansRight
      if (right - left < ansRight - ansLeft) {
        ansLeft = left;
        ansRight = right;
      }
      // 左端点字母离开窗口
      arrS[s[left].charCodeAt()] -= 1;
      left += 1;
    }
  }
  return ansLeft < 0 ? '' : s.substring(ansLeft, ansRight + 1);
}

var maxSubArray = function (nums) {
  var res = nums[0];
  // sum 表示当前最大的子数组之和
  var sum = 0;
  for (var n of nums) {
    if (sum > 0) {
      sum += n;
    } else {
      sum = n;
    }
    res = Math.max(res, sum);
  }
  return res;
}

var merge = function (intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  var res = [];
  for (var p of intervals) {
    var len = res.length;
    // 若列表为空，或当前区间和上一个区间不重合，直接添加
    if (len <= 0 || p[0] > res[len - 1][1]) {
      res.push(p);
    } else {
      // 区间重合，更新 res 中最后一个区间的右端点
      res[len - 1][1] = Math.max(p[1], res[len - 1][1]);
    }
  }
  return res;
}

// 方法一：使用额外的数组
var rotate = function (nums, k) {
  var len = nums.length;
  var arr = new Array(len);
  for (var i = 0; i < len; i++) {
    arr[(i + k) % len] = nums[i];
  }
  for (var j = 0; j < len; j++) {
    nums[j] = arr[j];
  }
}

// 方法二：翻转数组
var rotate = function (nums, k) {
  var reverse = function (start, end) {
    while (start <= end) {
      [nums[start], nums[end]] = [nums[end], nums[start]];
      start += 1;
      end -= 1;
    }
  }
  var len = nums.length;
  k = k % len;
  reverse(0, len - 1);
  reverse(0, k - 1);
  reverse(k, len - 1);
}

var productExceptSelf = function (nums) {
  var len = nums.length;
  var res = new Array(len).fill(1);
  var left = 0, right = len - 1;
  var lp = 1, rp = 1;
  while (left < len && right >= 0) {
    res[left] *= lp;
    res[right] *= rp;
    lp *= nums[left++];
    rp *= nums[right--];
  }
  return res;
}

// 使用除法的做法
var productExceptSelf = function(nums) {
  var len = nums.length;
  var product = 1;
  var zeroCount = 0;
  var zeroIndex = -1;
  for (var k = 0;k < len;k++) {
    if (nums[k] !== 0) {
      // 计算所有非零元素的乘积
      product *= nums[k];
    } else {
      zeroCount += 1;
      zeroIndex = k;
    }
  }
  
  var res = new Array(len).fill(0);
  // 有两个及以上0，结果就都是0
  if (zeroCount >= 2) {
    return res;
  }

  // 有1个0，除了0那一位，其它都是0
  if (zeroCount === 1) {
    res[zeroIndex] = product;
    return res;
  }

  // 没有0，每个位置的值就是所有元素乘积除以自身
  for (var i = 0;i < nums.length;i++) {
    res[i] = product / nums[i];
  }
  return res;
}

// 方法一：哈希表，空间复杂度O(n)不满足要求
var firstMissingPositive = function(nums) {
  var map = new Map();
  for (var n of nums) {
    map.set(n, n);
  }
  var k = 1;
  while (true) {
    if (!map.has(k)) {
      return k;
    }
    k += 1;
  }
}

// 方法二：数组，空间复杂度O(1)
var firstMissingPositive = function(nums) {
  var len = nums.length;
  // 将数组中所有小于等于 0 的数修改为 N+1
  for (var i = 0;i < len;i++) {
    if (nums[i] <= 0) {
      nums[i] = len + 1;
    }
  }
  for (var j = 0;j < len;j++) {
    // 将 |num| - 1 位置的元素添加负号
    var num = Math.abs(nums[j]);
    if (num <= len) {
      nums[num - 1] = -Math.abs(nums[num - 1]);
    }
  }
  for (var k = 0;k < len;k++) {
    if (nums[k] > 0) {
      return k + 1;
    }
  }
  return k + 1;
}

// 方法三：置换，空间复杂度O(1)
var firstMissingPositive = function(nums) {
  var len = nums.length;
  for (var i = 0;i < len;i++) {
    // 只需要处理正整数，把x放到下标为x-1的位置
    // 注意这里不能用变量接收nums[i]，因为nums[i]的值会改变
    while(nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] !== nums[i]) {
      var temp = nums[i];
      nums[i] = nums[nums[i] - 1];
      nums[temp - 1] = temp;
    }
  }
  for (var j = 0;j < len;j++) {
    if (nums[j] !== j + 1) {
      return j + 1;
    }
  }
  return len + 1;
}

// 方法一：使用标记数组
var setZeroes = function(matrix) {
  // m 为行数，n 为列数
  var m = matrix.length, n = matrix[0].length;
  var row = new Array(m).fill(false);
  var col = new Array(n).fill(false);

  // 遍历矩阵，记录下0所在的行和列
  for (var i = 0;i < m;i++) {
    for (var j = 0;j < n;j++) {
      if (matrix[i][j] === 0) {
        row[i] = col[j] = true;
      }
    }
  }

  // 遍历矩阵，更新原矩阵，将0所在行和列的元素置为0
  for (var i = 0;i < m;i++) {
    for (var j = 0;j < n;j++) {
      if (row[i] || col[j]) {
        matrix[i][j] = 0;
      }
    }
  }
}

// 方法二：使用两个标记变量
var setZeroes = function(matrix) {
  var m = matrix.length, n = matrix[0].length;
  var rowFlag = false, colFlag = false;

  // 记录第一行和第一列是否原本包含 0
  for (var j = 0;j < n;j++) {
    if (matrix[0][j] === 0) {
      rowFlag = true;
    }
  }
  for (var i = 0;i < m;i++) {
    if (matrix[i][0] === 0) {
      colFlag = true;
    }
  }

  // 从第二行第二列开始遍历，将0所在的行和列记录到第一行和第一列
  for (var i = 1;i < m;i++) {
    for (var j = 1;j < n;j++) {
      if (matrix[i][j] === 0) {
        matrix[0][j] = matrix[i][0] = 0;
      }
    }
  }

  // 再从第二行第二列开始遍历，根据第一行第一列更新矩阵元素是否为0
  for (var i = 1;i < m;i++) {
    for (var j = 1;j < n;j++) {
      if (matrix[0][j] === 0 || matrix[i][0] === 0) {
        matrix[i][j] = 0;
      }
    }
  }

  // 根据标记变量更新第一行和第一列
  if (rowFlag) {
    for (var j = 0;j < n;j++) {
      matrix[0][j] = 0;
    }
  }
  if (colFlag) {
    for (var i = 0;i < m;i++) {
      matrix[i][0] = 0;
    }
  }
}

var spiralOrder = function(matrix) {
  if (!matrix.length || !matrix[0].length) return [];
  var rows = matrix.length, cols = matrix[0].length;
  var left = 0, right = cols - 1, top = 0, bottom = rows - 1;
  var res = [];
  while (left <= right && top <= bottom) {
    for (var i = left;i <= right;i++) {
      res.push(matrix[top][i]);
    }
    top += 1;
    for (var i = top;i <= bottom;i++) {
      res.push(matrix[i][right]);
    }
    right -= 1;
    if (top <= bottom) {
      for (var i = right;i >= left;i--) {
        res.push(matrix[bottom][i]);
      }
    }
    bottom -= 1;
    if (left <= right) {
      for (var i = bottom;i >= top;i--) {
        res.push(matrix[i][left]);
      }
    }
    left += 1;
  }
  return res;
}