9. 搜索旋转排序数组
题⽬描述
给你⼀个升序排列的整数数组 nums ，和⼀个整数 target 。
假设按照升序排序的数组在预先未知的某个点上进⾏了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变 为 [4,5,6,7,0,1,2] ）。
请你在数组中搜索 target ，如果数组中存在这个⽬标值，则返回它的索引，否则返回 -1 。
示例 1：
输⼊：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输⼊：nums = [4,5,6,7,0,1,2], target = 3
输出：-1 示例 3：
输⼊：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独⼀⽆⼆
nums 肯定会在某个点上旋转
-10^4 <= target <= 10^4
思路
这是⼀个我在⽹上看到的前端头条技术终⾯的⼀个算法题。
题⽬要求时间复杂度为 logn，因此基本就是⼆分法了。
这道题⽬不是直接的有序数组，不然就 是 easy 了。
⾸先要知道，我们随便选择⼀个点，将数组分为前后两部分，其中⼀部分⼀定是有序的。
具体步骤：
我们可以先找出 mid，然后根据 mid 来判断，mid 是在有序的部分还是⽆序的部分
假如 mid ⼩于 start，则 mid ⼀定在右边有序部分。
假如 mid ⼤于等于 start， 则 mid ⼀定在左边有序部分。 注意等号的考虑 然后我们继续判断 target 在哪⼀部分， 我们就可以舍弃另⼀部分了 我们只需要⽐较 target 和有序部分的边界关系就⾏了。
⽐如 mid 在右侧有序部分，即[mid, end] 那么我们只需要判断 target >= mid && target <= end 就能知道 target 在右侧有序部分，我们就 可以舍弃左边部分了(start = mid + 1)， 反之亦然。
我们以([6,7,8,1,2,3,4,5], 4)为例讲解⼀下：
关键点解析
⼆分法
找出有序区间，然后根据 target 是否在有序区间舍弃⼀半元素
代码
/*
* @lc app=leetcode id=33 lang=javascript
*
* [33] Search in Rotated Sorted Array
* */
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function (nums, target) {
// 时间复杂度：O(logn)
// 空间复杂度：O(1)
// [6,7,8,1,2,3,4,5]
let start = 0;
let end = nums.length - 1;
while (start <= end) {
const mid = start + ((end - start) >> 1);
if (nums[mid] === target) return mid;
// [start, mid]有序
// ⚠ 注意这⾥的等号
if (nums[mid] >= nums[start]) {
//target 在 [start, mid] 之间
// 其实target不可能等于nums[mid]， 但是为了对称，我还是加上了等号
if (target >= nums[start] && target <= nums[mid]) {
end = mid - 1;
} else {
//target 不在 [start, mid] 之间
start = mid + 1;
}
} else {
// [mid, end]有序
// target 在 [mid, end] 之间
if (target >= nums[mid] && target <= nums[end]) {
start = mid + 1;
} else {
// target 不在 [mid, end] 之间
end = mid - 1;
}
}
}
return -1;
};复杂度分析
时间复杂度：O(logN)
空间复杂度：O(1)
10. 组合总和
题⽬描述
给定⼀个⽆重复元素的数组 candidates 和⼀个⽬标数 target ，找出 candidates 中所有可以使
数字和为 target 的组合。
candidates 中的数字可以⽆限制重复被选取。
说明： 所有数字（包括 target）都是正整数。 解集不能包含重复的组合。
示例 1：
输⼊：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ]
示例 2： 输⼊：candidates = [2,3,5], target = 8, 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]
提示：
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独⼀⽆⼆的。
1 <= target <= 500
前置知识
回溯法
代码
function backtrack(list, tempList, nums, remain, start) {
if (remain < 0) return;
else if (remain === 0) return list.push([...tempList]);
for (let i = start; i < nums.length; i++) {
tempList.push(nums[i]);
backtrack(list, tempList, nums, remain - nums[i], i); // 数字可以重复使⽤， i + 1代表不可以重复利⽤
tempList.pop();
}
}
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
const list = [];
backtrack(
list,
[],
candidates.sort((a, b) => a - b),
target,
0
);
return list;
};
11. 接⾬⽔
题⽬描述
给定 n 个⾮负整数表示每个宽度为 1 的柱⼦的⾼度图，计算按此排列的柱⼦，下⾬之后能接多少⾬⽔。
上⾯是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的⾼度图，在这种情况下，可以接 6 个单位的⾬⽔（蓝⾊部分表示⾬⽔）。
示例: 输⼊: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6
前置知识
空间换时间
双指针
单调栈
双数组
思路
这是⼀道⾬⽔收集的问题， 难度为 hard . 如图所示，让我们求下过⾬之后最多可以积攒多少的 ⽔。
如果采⽤暴⼒求解的话，思路应该是 height 数组依次求和，然后相加。
伪代码
for (let i = 0; i < height.length; i++) {
area += (h[i] - height[i]) * 1; // h为下⾬之后的⽔位
}问题转化为求 h，那么 h[i]⼜等于 左右两侧柱⼦的最⼤值中的较⼩值 ，即 h[i] = Math.min(左边柱⼦最⼤值, 右边柱⼦最⼤值)
如上图那么 h 为 [0, 1, 1, 2, 2, 2 ,2, 3, 2, 2, 2, 1]
问题的关键在于求解 左边柱⼦最⼤值 和 右边柱⼦最⼤值 , 我们其实可以⽤两个数组来表示 leftMax , rightMax ， 以 leftMax 为例，leftMax[i]代表 i 的左侧柱⼦的最⼤值，因此我们维护两个数组即可。 关键点解析 建模 h[i] = Math.min(左边柱⼦最⼤值, 右边柱⼦最⼤值) (h 为下⾬之后的⽔位)
代码
/*
* @lc app=leetcode id=42 lang=javascript
*
* [42] Trapping Rain Water
*
*/
/**
* @param {number[]} height
* @return {number}
*/
var trap = function (height) {
let max = 0;
let volume = 0;
const leftMax = [];
const rightMax = [];
for (let i = 0; i < height.length; i++) {
leftMax[i] = max = Math.max(height[i], max);
}
max = 0;
for (let i = height.length - 1; i >= 0; i--) {
rightMax[i] = max = Math.max(height[i], max);
}
for (let i = 0; i < height.length; i++) {
volume = volume + Math.min(leftMax[i], rightMax[i]) - height[i];
}
return volume;
};
12. 全排列
题⽬描述
给定⼀个 没有重复 数字的序列，返回其所有可能的全排列。
示例: 输⼊: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
前置知识
回溯
思路
回溯的基本思路清参考上⽅的回溯专题。
以 [1,2,3] 为例，我们的逻辑是： 先从 [1,2,3] 选取⼀个数。 然后继续从 [1,2,3] 选取⼀个数，并且这个数不能是已经选取过的数。 如何确保这个数不能是已经选取过的数？我们可以直接在已经选取的数字中线性查找，也 可以将已经选取的数字中放到 hashset 中，这样就可以在 的时间来判断是否已经被 选取了，只不过需要额外的空间。 重复这个过程直到选取的数字个数达到了 3。
关键点解析
回溯法
backtrack 解题公式
代码
function backtrack(list, tempList, nums) {
if (tempList.length === nums.length) return list.push([...tempList]);
for (let i = 0; i < nums.length; i++) {
if (tempList.includes(nums[i])) continue;
tempList.push(nums[i]);
backtrack(list, tempList, nums);
tempList.pop();
}
}
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function (nums) {
const list = [];
backtrack(list, [], nums);
return list;
};复杂度分析
时间复杂度：O（N!）
空间复杂度：O(N)
13.两数之和
题⽬描述
给定⼀个整数数组 nums 和⼀个⽬标值 target，请你在该数组中找出和为⽬标值的那 两个 整 数，并返回他们的数组下标。
你可以假设每种输⼊只会对应⼀个答案。但是，数组中同⼀个元素不能使⽤两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
解题思路
对于这道题，我们很容易想到使⽤两层循环来解决这个问题，但是两层循环的复杂度为O （n2），我们可以考虑能否换⼀种思路，减⼩复杂度。
这⾥使⽤⼀个map对象来储存遍历过的数字以及对应的索引值。我们在这⾥使⽤减法进⾏计算
计算target和第⼀个数字的差，并记录进map对象中，其中两数差值作为key，其索引值作为value。
再计算第⼆个数字与target的差，并与map对象中的数值进⾏对⽐，若相同，直接返回，如果 没有相同值，就将这个差值也存⼊map对象中。
重复第⼆步，直到找到⽬标值。
代码实现
/*
@param {number[]} nums
@param {number} target
@return {number[]}
*/
var twoSum = function (nums, target) {
const maps = {};
const len = nums.length;
for (let i = 0; i < len; i++) {
if (maps[target - nums[i]] !== undefined) {
return [maps[target - nums[i]], i];
}
maps[nums[i]] = i;
}
};14.三数之和
题⽬描述
给你⼀个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满⾜条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
解题思路
这个题和之前的两数之和完全不⼀样，不过这⾥依旧可以使⽤双指针来实现。 我们在使⽤双指针时，往往数组都是有序的，这样才能不断缩⼩范围，所以我们要对已知数组 进⾏排序。
（1）⾸先我们设置⼀个固定的数，然后在设置两个指针，左指针指向固定的数的后⾯那个值， 右指针指向最后⼀个值，两个指针相向⽽⾏。
（2）每移动⼀次指针位置，就计算⼀下这两个指针与固定值的和是否为0，如果是，那么我们 就得到⼀组符合条件的数组，如果不是0，就有⼀下两种情况： 相加之和⼤于0，说明右侧值⼤了，右指针左移 相加之和⼩于0，说明左侧值⼩了，左指针右移
（3）按照上边的步骤，将前len-2个值依次作为固定值，最终得到想要的结果。 因为我们需要三个值的和，所以我们⽆需最后两个值作为固定值，他们后⾯已经没有三个值可 以进⾏计算了。
代码
/**
@param {number[]} nums
@return {number[][]}
*/
var threeSum = function (nums) {
let res = [];
let sum = 0;
// 将数组元素排序
nums.sort((a, b) => {
return a - b;
});
const len = nums.length;
for (let i = 0; i < len - 2; i++) {
let j = i + 1;
let k = len - 1;
// 如果有重复数字就跳过
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
while (j < k) {
// 三数之和⼩于0，左指针右移
if (nums[i] + nums[j] + nums[k] < 0) {
j++;
// 处理左指针元素重复的情况
while (j < k && nums[j] === nums[j - 1]) {
j++;
}
// 三数之和⼤于0，右指针左移
} else if (nums[i] + nums[j] + nums[k] > 0) {
k--;
// 处理右指针元素重复的情况
while (j < k && nums[k] === nums[k + 1]) {
k--;
}
} else {
// 储存符合条件的结果
res.push([nums[i], nums[j], nums[k]]);
j++;
k--;
while (j < k && nums[j] === nums[j - 1]) {
j++;
}
while (j < k && nums[k] === nums[k + 1]) {
k--;
}
}
}
}
return res;
};
