旋转数组、只出现一次的数字、两数之和、旋转图像
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例
输入: [1,2,3,4,5,6,7] 和 k = 3输出: [5,6,7,1,2,3,4]解释:向右旋转 1 步: [7,1,2,3,4,5,6]向右旋转 2 步: [6,7,1,2,3,4,5]向右旋转 3 步: [5,6,7,1,2,3,4]
思路
数据元素向右移动 1 个位置，相当于将数组元素的最后一项截取，然后放到第一项的位置，因此向右移动 k 个位置，就是循环执行上述操作 k 次。而当 k 为数组长度的倍数时，实际相当于没有移动，所以实际需要循环操作的次数为 k % l。
详解
首先计算出需要循环移动的次数；
通过数组的
unshift()和pop()方法实现旋转，循环执行 k 次。
unshift() 方法将把它的参数插入数组的头部，并将已经存在的元素顺次地移到较高的下标处，该方法不会创建新数组，而是直接修改原数组。
pop() 方法将删除数组的最后一个元素，把数组长度减 1，并且返回它删除的元素的值。
/*** @param {number[]} nums* @param {number} k* @return {void} Do not return anything, modify nums in-place instead.*/const rotate = function (nums, k) {const l = nums.length;k = k % l;for (let i = 0; i < k; i++) {nums.unshift(nums.pop());}};
复杂度分析
时间复杂度：
循环遍历的次数取决于k的值，与k值呈线性关系，因此复杂度为 。
空间复杂度：
没有申请额外的空间，因此复杂度为 。
思路
方法一是将数组中的元素一个一个移动，我们还可以一次性将最后的 k % l 项全部截取，通过扩展运算符‘...’将截取的值放到数组的前边，实现旋转。
详解
首先还是计算出需要截取的数组元素的长度；
通过数组的
splice()方法截取需要移动的元素，然后使用扩展运算符‘...‘将截取的元素当作参数，通过 unshift() 方法将截取的 元素放到数组的前边。
splice() 方法可删除从 index 处开始的零个或多个元素，然后返回被删除的项目。
数组的扩展运算符...相当于将数组展开,主要的使用场景是用于数组复制、合并等。
unshift() 方法的第一个参数将成为数组的 index 为0的新元素，如果还有第二个参数，它将成为 index 为1的新元素，以此类推。
/*** @param {number[]} nums* @param {number} k* @return {void} Do not return anything, modify nums in-place instead.*/const rotate = function (nums, k) {const l = nums.length;k = k % l;nums.unshift(...nums.splice(l - k, k));};
时间复杂度：。 采用一次性截取，所有方法都只执行了 1 次，因此复杂度为 。
空间复杂度：。没有申请额外的空间，因此复杂度为 。
先将原数组的所有元素整体往后移动 k 个位置，给需要旋转的元素预留出位置，然后通过替换和删除，实现数组的旋转。
详解
先将原数组原有的元素从最后一位开始，依次移动到（原下标 + k）的位置；
然后再从改变后的新数组的下标为 (k - 1) 的元素开始，依次将最后一位赋值给新数组下标为 (k - 1) 的元素，然后删除掉最后一位元素。
/*** @param {number[]} nums* @param {number} k* @return {void} Do not return anything, modify nums in-place instead.*/const rotate = function (nums, k) {const l = nums.length;k = k % l;for (let i = l - 1; i >= 0; i--) {nums[i + k] = nums[i];}for (let j = k - 1; j >= 0; j--) {nums[j] = nums[l + j];nums.pop();}};
复杂度分析：
时间复杂度：
循环遍历的次数取决于数组长度，与数组长度呈线性关系，因此复杂度为 。
空间复杂度：
数组进行了扩充，申请了n个空间，因此复杂度为 。
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例 1:
输入: [2,2,1]输出: 1
示例 2:
输入: [4,1,2,1,2]输出: 4
思路
将数组遍历，并通过过滤的方法，将值相同的数归集为数组的一个元素，由于除了一个元素，其他元素都会出现两次，所有只要找到过滤的集合的长度为1的那个集合，该集合第一个元素即是该元素。
详解
遍历数组，由于需要返回值，这里使用map方法
使用过滤函数，过滤数组中值与当前遍历的元素的值相同的元素
现在得到了一个存在多个集合的数组，而数组中唯一值的那个元素的集合肯定值存在它自己
查询这个集合中长度只有1的集合，再取这个集合的第一个元素，即是只出现一次的数字
代码
const singleNumber = (nums) => {const numsGroup = nums.map(num => nums.filter(v => v === num));return numsGroup.find(num => num.length === 1)[0];};
复杂度分析
时间复杂度：
使用了
map和filter，嵌套遍历，故为。空间复杂度：
map方法创建了一个长度为的数组，占用了大小的空间。
思路
异或运算符可以将两个数字比较，由于有一个数只出现了一次，其他数皆出现了两次，类似乘法法则无论先后顺序，最后相同的数都会异或成0，唯一出现的数与0异或就会得到其本身，该方法是最优解，直接通过比较的方式即可得到只出现一次的数字。
详解
将数组的一个元素与下一个元素做异或比较，直接使用reduce方法
两两异或最后与所有元素都不相同，最后返回的值即是只出现一次的数字。
代码
const singleNumber = (nums) => {return nums.reduce((accumulator, currentValue) => accumulator ^ currentValue);};
复杂度分析
时间复杂度：
仅用
reduce方法遍历，一层遍历，故为。空间复杂度：
空间复杂度为常量，占用空间没有随数据量 的大小发生改变，故为。
给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
示例
给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]
思路
遍历每个元素 x，并查找是否存在一个值与 target - x 相等的目标元素。
详解
遍历每个元素
x并查找是否存在一个值与
target - x相等的目标元素。
const twoSum = function (nums, target) {for (let i = 0; i < nums.length; i++) {for (let j = i + 1; j < nums.length; j++) {if (nums[j] === target - nums[i]) {return [i, j];}}}};
复杂度分析
时间复杂度：
对于每个元素，通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 的时间。
空间复杂度：
没有申请额为的空间，所以空间复杂度为 。
思路
将每个元素的值和它的索引加到表中，检查每个元素所对应的目标元素（target - nums[i]）是否存在于表中
详解
将每个元素的值和它的索引添加到表中
检查每个元素所对应的目标元素（target - nums[i]）是否存在于表中
代码
const twoSum = function (nums, target) {const lookup = {};let res = [];nums.some((v, i) => {if (lookup[target - v] !== undefined) {res = [lookup[target - v], i];return true;} else {lookup[v] = i;return false;}});return res;};
复杂度分析
时间复杂度：
我们只遍历了包含有 n 个元素的列表一次，在
map中进行的每次查找只花费 的时间, 因此总的复杂度为 空间复杂度：
上述解法中，申请了大小为 的空间，空间复杂度跟数字的个数 n 线性相关，因此为 。
给定一个 n × n 的二维矩阵表示一个图像，将图像顺时针旋转 90 度。
必须在原地旋转图像，需要直接修改输入的二维矩阵，不要使用另一个矩阵来旋转图像。
示例
给定 matrix =[[1,2,3],[4,5,6],[7,8,9]],原地旋转输入矩阵，使其变为:[[7,4,1],[8,5,2],[9,6,3]]
给定 matrix =[[ 5, 1, 9,11],[ 2, 4, 8,10],[13, 3, 6, 7],[15,14,12,16]],原地旋转输入矩阵，使其变为:[[15,13, 2, 5],[14, 3, 4, 1],[12, 6, 8, 9],[16, 7,10,11]]
思路
找到一个矩阵中对应点的旋转90度需要涉及到的四个位置的数字，然后将对应的四个数字按照顺时针90度的方法交换即可。
详解
根据输入得到矩阵的维数；
以左上角为（0，0）点，从左向右递增，从上向下递增建立矩阵；
将需要矩阵上需要交换的四个数字存放在一个临时数组中；
将原本位置上的数据按照数组中的数据进行替换。
代码
function rotate (matrix) {const n = matrix.length; // n维矩阵for (let i = 0; i < n; i++) {for (let j = i; j < n - i - 1; j++) {const a = [matrix[i][j], matrix[j][n - 1 - i], matrix[n - 1 - i][n - 1 - j], matrix[n - 1 - j][i]];matrix[i][j] = a[3];matrix[j][n - 1 - i] = a[0];matrix[n - 1 - i][n - 1 - j] = a[1];matrix[n - 1 - j][i] = a[2];}}}
复杂度分析
时间复杂度：
将矩阵进行遍历，二维数组需循环遍历两次，则复杂度为
空间复杂度：
所占用空间不会随矩阵的维数而有所变化
思路
先将矩阵沿左上角到右下角的对角线进行对称，然后将矩阵沿垂直中线对称即可。
详解
根据输入得到矩阵的维数；
以左上角为（0，0）点，从左向右递增，从上向下递增建立矩阵；
将矩阵沿左上角到右下角的对角线进行对称，以题目例子 1 为例即:
[[1,4,7],[2,5,8],[3,6,9]]
再将矩阵沿垂直中线进行对称。即:
[[7,4,1],[8,5,2],[9,6,3]]
代码
function rotate (matrix) {const n = matrix.length;// 调换对角线元素for (let i = 0; i < n; i++) {for (let j = i; j < n; j++) {const temp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = temp;}}// 调换每行的左右元素for (let k = 0; k < n; k++) {for (let l = 0; l < Math.floor(n / 2); l++) {const temp = matrix[k][l];matrix[k][l] = matrix[k][n - 1 - l];matrix[k][n - 1 - l] = temp;}}}
复杂度分析
时间复杂度：
将矩阵进行遍历，二维数组需循环遍历两次，则复杂度为
空间复杂度：
所占用空间不会随矩阵的维数而有所变化
思路
先将矩阵沿右上角到左下角的对角线进行对称，然后将矩阵沿水平中线对称即可。
详解
根据输入得到矩阵的维数；
将矩阵沿右上角到左下角的对角线进行对称，以题目例子 1 为例即:
[[9,6,3],[8,5,2],[7,4,1]]
将矩阵沿水平中线进行对称。即：
[[7,4,1],[8,5,2],[9,6,3]]
代码
function rotate (matrix) {const n = matrix.length;// 按对角线调换数字for (let i = 0; i < n; i++) {for (let j = 0; j < n - 1 - i; j++) {const temp = matrix[i][j];matrix[i][j] = matrix[n - 1 - j][n - 1 - i];matrix[n - 1 - j][n - 1 - i] = temp;}}// 从头到尾交换每一行for (let k = 0; k < Math.floor(n / 2); k++) {const temp = matrix[k];matrix[k] = matrix[n - 1 - k];matrix[n - 1 - k] = temp;}}
复杂度分析
时间复杂度：
将矩阵进行遍历，二维数组需循环遍历两次，则复杂度为
空间复杂度：
空间与矩阵维数正相关
