LeetCode(力扣)答案解析（一） #2
Description
1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]解法一（暴力法）
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
var len = nums.length;
for (var i = 0; i < len; i++) {
for (var j = i + 1; j < len; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
};暴力法是纯粹枚举所有组合的和，是否与target的值相等。
解法二（两次哈希遍历）
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
var len = nums.length;
var hashMap = {};
for (var i = 0; i < len; i++) {
// 记录每个数值对应数组的下标
hashMap[nums[i]] = i;
}
for (var i = 0; i < len; i++) {
// 计算差值
var res = target - nums[i];
// 若差值在hashMap存在，且下标不相等（题目要求不相同的数）
if (hashMap[res] && hashMap[res] !== i) {
return [i, hashMap[res]];
}
}
return [];
};两次哈希遍历，利用了对象中的key唯一性，而其值存放该key在nums数组下的下标，方便后面对比和组织返回结果。虽然两次哈希遍历需要额外的存储空间，但比暴力法快了不少，这就是时间和空间上作出的权衡，然而，这种方法并不是最快的方法。
解法三（一次哈希遍历）
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
var len = nums.length;
var hashMap = {};
for (var i = 0; i < len; i++) {
var res = target - nums[i];
if (hashMap[res] || hashMap[res] !== 0) { // 兼容下标为0的情况
return [hashMap[res], i];
}
hashMap[nums[i]] = i;
}
return [];
};一次哈希遍历在时间复杂度和两次哈希遍历是一样的，但是一次哈希遍历，少了一次遍历nums数组。这里的思路是：一边构造hashMap，一边用target减去当前遍历到下标为i的nums数组中的数，看差值是否在hashMap中，若存在，则返回结果，若不存在，则继续扫描后面的数。
136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例1:
输入: [2,2,1]
输出: 1示例2:
输入: [4,1,2,1,2]
输出: 4解法一（暴力法 + 双重循环）
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
var len = nums.length;
for (var i = 0; i < len; i++) {
var isSame = false;
for (var j = 0; j < len; j++) {
// 两数下标不同，且值相同
if (i !== j && nums[i] === nums[j]) {
// 标志已经找到了相同的数
isSame = true;
// 跳出当前循环
break;
}
}
// 若不存在相同的数
if (!isSame) {
return nums[i];
}
}
return null;
};这个解法真的暴力，既耗时，也违反题目要求（线性时间），但是这个是最直接的做法。
解析二（线性时间 + 借助对象排重）
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
var len = nums.length;
var obj = {};
for (var i = 0; i < len; i++) {
var num = nums[i];
// 判断该数是否存在键值对，若有其值加1，若没有，初始化其值为1
obj[num] ? obj[num]++ : obj[num] = 1;
}
for (var item in obj) {
// 若该数只出现一次
if (obj[item] === 1) {
return item;
}
}
return null;
};这个方法，运用了对象的key唯一的特性来区分统计数组中的值出现次数，最后遍历一次对象，匹配出其值为1的key值，这就是答案了。虽然这个方法有着不错的性能，但是还是违反题目中不能运用额外的空间的要求。
解法三（遍历数组逐一异或（^））
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
var len = nums.length;
var result = 0;
for (var i = 0; i < len; i++) {
result = result ^ nums[i];
}
return result;
};What？异或是什么？我是谁？我在哪里？别急，异或其实很好理解。异或，是JavaScript和很多其他高级语言的位运算符，我们把这个运算过程叫做位运算。异或是指两数对应位数的值不同则返回1，若相同则返回0。举个例子1 ^ 1 = 0, 而 1 ^ 0 = 1。利用这个特性，我抓住题意中：数组中只有一个数字出现一次，其它数字均出现两次。那么两个相同的数异或永远等于0，而0与任何数，都等于其数本身。利用这个特性，我们可以逐一遍历数组中的数，然后逐一异或，得到最后的结果，就是只出现一次的数字了。异或详细讲解
231. 2的幂
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
示例1:
输入：1
输出：true
解释：2的0次方 = 1示例2:
输入: 16
输出: true
解释: 2的4次方 = 16示例3:
输入: 218
输出: false解法一（对数求值 + 求整对比）
/**
* @param {number} n
* @return {boolean}
*/
var isPowerOfTwo = function(n) {
var temp = Math.log2(n);
return temp === Math.floor(temp);
};这个方法是纯粹式数学思维解题。
解法二（求与对比）
/**
* @param {number} n
* @return {boolean}
*/
var isPowerOfTwo = function(n) {
return n <= 0 ? false : (n & (n-1)) === 0;
};这个方法非常巧妙。经过我们分析，2的n次方，例如2、4、8、16 ... 对应的二进制为10、100、1000、10000 ... 可以看到，2的n次方对应其二进制数，都是开头1然后后面跟着全是0，那么当这个数减1之后，开头就变成了0，后面跟着全是1。例如2 - 1 = 1 = 01(二进制) 、4 - 1 = 3 = 011(二进制)、8 - 1 = 7 = 0111(二进制) ... 可以发现，2的n次幂与自身减1相与，那么，结果必定是0，数字1同样适用这个规律(1 & 0 = 0)。