中级算法 数组

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

TIP

最简单粗暴的思路就是直接两层循环加一个Map来搞定，再用一个Map来判断三元组是否重复

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  const map = {};
  nums.forEach((num, index) =>{
    map[num] = index
  })
  const result = [];
  const resultMap = {};
  for(let i = 0; i < nums.length - 2; i++ ){
    const curr_i = nums[i];
    for(let j = i + 1;  j < nums.length - 1; j++ ){
      const curr_j = nums[j];
      const curr_k = 0 - (curr_i + curr_j );
      if (map[curr_k] > j) {
        const temp = [curr_i, curr_j, curr_k];
        const temp_key = temp.sort().join(',')
        if(!resultMap[temp_key]){
          result.push(temp)
        }
        resultMap[temp_key] = 1
      }
    }
  }
  return result;
};

const nums = [0, 1 ,1];
const result = threeSum(nums);
console.log(result.length === 0);

const nums = [0, 0, 0];
const result = threeSum(nums);
console.log(result.length === 1);

矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

进阶：

• 一个直观的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
• 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
• 你能想出一个仅使用常量空间的解决方案吗？

TIP

一个简单的思路就是用两个数组存储行列是否需要置零，这样就是O(m + n) 的额外空间。 进一步，我们可以利用第一列和第一行来存储这些信息，再额外用两个变量表示第一行和第一列是否需要置零，这样就是 O(2) 的额外空间。

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
  // 代码就不写了
};

字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

TIP

关键思路就是生成一个字母异位词的唯一标识，将相同标识的词归成一类即可。

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
  const result = [];
  const map = {};
  strs.forEach(str => {
    const key = generateKey(str);
    if(!map[key]){
      map[key] = [];
    }
    map[key].push(str)
  });
  Object.keys(map).forEach(key => {
    const list = map[key];
    result.push(list);
  })
  return result;
};

var generateKey = function(str){
  const charList = str.split('');
  const charListBySort = charList.sort((a, b) => a.localeCompare(b));
  const charKey = charListBySort.join('');
  return charKey;
}