快乐数 && 两个数组的交集 && 有效的字母异位词

快乐数

这是力扣 202 题

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」  定义为： 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为  1，那么这个数就是快乐数。 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

解题思路

这道题题目十分简短，但是并不是像表面一样那么容易。它有很多种解法，比如哈希法，双指针法。由于考虑到时间复杂度的问题，所以这次主要来讲一下时间复杂度更低的双指针法，这里又称快慢指针法。

双指针法

这道题我们可以换个思路，简化一下，理解成如下这样： 我们把它想像成快跑者和慢跑者。 如果 n 是一个快乐数，即没有循环，那么快跑者最终会比慢跑者先到达数字 1。 如果 n 不是一个快乐的数字，那么最终快跑者和慢跑者将在同一个数字上相遇。

所以可以创建两个指针，分别是快指针和慢指针，整体思路如下：

• 首先创建一个慢指针，规定一次移动一步，再创建一个快指针，规定一次移动两步。
• 当快慢指针相遇时，代表形成环路，说明该数不是快乐数。
• 若指针移动过程中，最终找到了 1，则说明当前数是一个快乐数。
• 最后 return 返回最终结果

相关代码如下：

var isHappy = function (n) {
	    let slow = n;
	    // 有可能第一步就判断出是快乐数
	    let fast = getNext(n);
	    while (fast !== 1) {
	        slow = getNext(slow);
	        fast = getNext(getNext(fast));
	        if (slow === fast) {
	            return false;
	        }
	    }
	    return fast === 1;
	}
	let getNext = function (n) {
	    let sum = 0;
	    while (n > 0) {
	        sum += Math.pow(n % 10, 2);
	        n = Math.floor(n / 10);
	    }
	    return sum;
	}

根据思路对着代码不断演示，这样就可以理清楚其中的关系了。

两个数组的交集

这是力扣 349 题

给定两个数组  nums1  和  nums2 ，返回  它们的交集 。输出结果中的每个元素一定是  唯一  的。我们可以  不考虑输出结果的顺序 。

解题思路

在上一篇有关哈希表的文章里就提到过，如果当我们遇到要判断一个元素是否出现集合里的题目的时候，就可以考虑哈希表法。因此，这题首选哈希表法。

哈希表法

我们不用考虑输出结果的排序，因为题目上已经说明输出元素的结果是唯一的。对于这道题，这里要用到哈希表的另一种结果体，Set。在 Set 中，Set 对象存储的值总是唯一的。将数组通过 Set 存储后，然后进行比较，判断是否存在相同的值。

大概思路如下： 先将数组转成 Set，然后遍历长度小的 Set，判断长度小的 Set 中的元素是否存在于长度大的 Set 中，存在的话就是其中一个交集。

相关代码如下：

var intersection = function(nums1, nums2) {
  let set1 = null
  let set2 = null
  let arr = []
  // set1中的长度长
  if (nums1.length >= nums2.length) {
    set1 = new Set(nums1)
    set2 = new Set(nums2)
  } else {
    set1 = new Set(nums2)
    set2 = new Set(nums1)
  }
  for (let item of set2) {
    if (set1.has(item)) {
      arr.push(item)
    }
  }
  return arr
};

看到这里，是不是会觉得 Set 很强大，感觉哈希表的题目都可以通过 Set 来解决。其实并不是这样，如果在数据量特别大的情况下，使用 Set 会有特别大的耗时。现在因为数据量比较小，所以察觉不到这个耗时的差距。总之，使用 Set 会占用更多空间，而且比较耗时，这都是潜在的缺点，但是解决一下力扣题目当然是没有问题的。

有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。注意：若  s 和 t  中每个字符出现的次数都相同，则称  s 和 t  互为字母异位词。

解题思路

陆陆续续讲完一部分数组和链表的题目，现在到了哈希表的环节了。这道有效的字母异位词，有很多种解法，比如排序和哈希表，这里将重点介绍哈希表解法，以此来引出哈希表相关的知识。先简单说说哈希表吧，哈希表可以看成是数组，数组也可以看成是哈希表。当我们遇到要判断一个元素是否出现集合里的题目的时候，就可以考虑哈希表法。

排序

这道题的意思可以转换为两个字符串排序后相等。分别将两个字符串排序，然后比较两个排序后的字符串。排序法很简单，也很容易理解。

相关代码如下：

var isAnagram = function(s, t) {
    // 如果两个字符串长度不一样则不可能满足条件
    if (s.length !== t.length) {
        return false;
    }
    // 将字符串转为数组
    const arr1 = Array.from(s);
    const arr2 = Array.from(t);
    arr1.sort();
    arr2.sort();
    for (let i = 0; i < arr1.length; i++) {
        if (arr1[i] !== arr2[i]) {
            return false;
        }
    }
    return true;
};

哈希表法

如果用哈希表来解它，这道题的意思就可以转换成两个字符串中出现的字符种类和数量都相等。因此创建一个字母表，分别遍历并记录两个字符串，减去字母表中对应的数量。如果到了小于 0 的情况，说明其中一个字符串包含着另一个字符串不存在的字母。此处需要用到codePointAt() 方法返回一个 Unicode 编码点值的非负整数。

相关代码如下：

var isAnagram = function(s, t) {
 // 如果两个字符串长度不一样则不可能满足条件
    if (s.length !== t.length) {
        return false;
    }
    const hashtable = new Array(26).fill(0);
    for (let i = 0; i < s.length; ++i) {
        hashtable[s.codePointAt(i) - 'a'.codePointAt(0)]++;
    }
    for (let i = 0; i < t.length; ++i) {
        hashtable[t.codePointAt(i) - 'a'.codePointAt(0)]--;
        if (hashtable[t.codePointAt(i) - 'a'.codePointAt(0)] < 0) {
            return false;
        }
    }
    return true;
};