共计 10378 个字符，预计需要花费 26 分钟才能阅读完成。
数组操作的工夫复杂度
- Access：
O(1) - Search：
O(n) - Insert：均匀
O(n)，最好的状况下O(1)，也就是在数组尾部插入O(1)，最坏的状况下O(n) - Delete；均匀
O(n)，最好的状况下O(1)，也就是在数组尾部删除O(1)，最坏的状况下O(n)
167. 两数之和 II – 输出有序数组 (easy)
给你一个下标从 1 开始的整数数组 numbers，该数组已按 非递加顺序排列，请你从数组中找出满足相加之和等于指标数 target 的两个数。如果设这两个数别离是 numbers[index1] 和 numbers[index2]，则 1 <= index1 < index2 <= numbers.length。
以长度为 2 的整数数组 [index1, index2] 的模式返回这两个整数的下标 index1 和 index2。
你能够假如每个输出 只对应惟一的答案，而且你 不能够 重复使用雷同的元素。
你所设计的解决方案必须只应用常量级的额定空间。
示例 1：
输出：numbers = [2,7,11,15], target = 9
输入：[1,2]
解释：2 与 7 之和等于指标数 9。因而 index1 = 1, index2 = 2。返回 [1, 2]。
示例 2：输出：numbers = [2,3,4], target = 6
输入：[1,3]
解释：2 与 4 之和等于指标数 6。因而 index1 = 1, index2 = 3。返回 [1, 3]。
示例 3：输出：numbers = [-1,0], target = -1
输入：[1,2]
解释：-1 与 0 之和等于指标数 -1。因而 index1 = 1, index2 = 2。返回 [1, 2]。提醒：
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 非递加程序 排列
-1000 <= target <= 1000
仅存在一个无效答案
办法 1: 二分法
- 思路：循环数组，从以后元素左边的元素二分查找另一个元素，使他们的和是
target - 复杂度：工夫复杂度
O(nlogn)，遍历数组，每次遍历都进行了二分。空间复杂度O(1)
js：
var twoSum = function (numbers, target) {
let len = numbers.length,
left = 0,
right = len - 1,
mid = 0
for (let i = 0; i < len; ++i) {// 循环数组，从左边的元素二分查找另一个元素
left = i + 1
while (left <= right) {mid = parseInt((right - left) / 2) + left
if (numbers[mid] == target - numbers[i]) {return [i + 1, mid + 1]
} else if (numbers[mid] > target - numbers[i]) {right = mid - 1} else {left = mid + 1}
}
}
return [-1, -1]
}办法 2: 双指针
- 思路：应以 left 和 right 指针，初始别离在数组的两端，而后一直判断两个指针指向的数字之和 和 target 的大小，和大了，right 左移一位，和小了，left 右移一位
- 复杂度：工夫复杂度
O(n)，数组总共遍历一次。空间复杂度O(1)
js:
var twoSum = function (numbers, target) {let [left, right] = [0, numbers.length - 1];// 左右指针
while (left < right) {//
if (numbers[left] + numbers[right] > target) {// 和大了 right 左移一位
right--;
} else if (numbers[left] + numbers[right] < target) {// 和小了 left 右移一位
left++;
} else {return [left + 1, right + 1];
}
}
};349. 两个数组的交加 (easy)
给定两个数组 nums1 和 nums2，返回 它们的交加。输入后果中的每个元素肯定是 惟一 的。咱们能够 不思考输入后果的程序。
示例 1：
输出：nums1 = [1,2,2,1], nums2 = [2,2]
输入：[2]
示例 2：输出：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输入：[9,4]
解释：[4,9] 也是可通过的提醒：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
办法 1：汇合
- 思路：先将数组转成 set，而后遍历长度小的 set，判断 set1 中的元素是否存在于 set2 中，存在的话就是其中一个交加。
- 复杂度：工夫复杂度
O(m+n)，m，n 是两数组的长度，数组转成汇合的工夫复杂度就是数组的长度，遍历寻找交加的复杂度是O(min(m,n))。空间复杂度O(m+n)，就是两个 set 的空间
js：
var intersection = function (nums1, nums2) {let set1 = new Set(nums1);
let set2 = new Set(nums2);// 数组转成 set
if (set1.size > set2.size) {// 用 size 小的数组遍历
[set1, set2] = [set2, set1]
}
const intersection = new Set();
for (const num of set1) {// 遍历 set1
if (set2.has(num)) {// 元素如果不存在于 set2 中就退出 intersection
intersection.add(num);
}
}
return [...intersection];// 转成数组
};办法 2：排序 + 双指针
动画过大，点击查看
- 思路：数组排序，而后用两个指针别离遍历数组，如果两个指针指向的元素相等 就是其中一个交加，否则比拟两个指针指向的元素的大小，较小的向前挪动
- 复杂度：工夫复杂度
O(mlogm+nlogn)，两数组快排工夫复杂度别离是O(mlogm)、O(nlogn)，双指针遍历须要O(m+n)，复杂度取决于较大的O(mlogm+nlogn)。空间复杂度O(logm+logn)排序应用的额定空间
js：
// nums1 = [4,5,9]
// nums2 = [4,4,8,9,9]
// intersection = [4,9]
var intersection = function (nums1, nums2) {nums1.sort((x, y) => x - y);// 排序
nums2.sort((x, y) => x - y);
const length1 = nums1.length,
length2 = nums2.length;
let index1 = 0,// 双指针
index2 = 0;
const intersection = [];
while (index1 < length1 && index2 < length2) {// 双指针遍历数组
const num1 = nums1[index1],
num2 = nums2[index2];
if (num1 === num2) {// 如果两个指针指向的元素相等 就时其中一个交加
// 避免反复退出
if (num1 !== intersection[intersection.length - 1]) {intersection.push(num1);
}
index1++;
index2++;
} else if (num1 < num2) {index1++;//num1 < num2 阐明 mums1 须要向右挪动} else {index2++;//num1 > num2 阐明 mums1 须要向左挪动}
}
return intersection;
};217. 存在反复元素（easy）
给你一个整数数组 nums。如果任一值在数组中呈现 至多两次，返回 true；如果数组中每个元素互不雷同，返回 false。
示例 1：
输出：nums = [1,2,3,1]
输入：true
示例 2：输出：nums = [1,2,3,4]
输入：false
示例 3：输出：nums = [1,1,1,3,3,4,3,2,4,2]
输入：true提醒：
1 <= nums.length <= 105
-109 <= nums[i] <= 109
办法 1. 排序
- 思路：先排序，而后循环数组，判断相邻元素是否雷同
- 复杂度：工夫复杂度
O(nlogn)，空间复杂度O(logn)，排序须要的栈空间
js：
var containsDuplicate = function(nums) {nums.sort((a, b) => a - b);// 排序
const n = nums.length;
for (let i = 0; i < n - 1; i++) {if (nums[i] === nums[i + 1]) {// 判断相邻元素是否雷同
return true;
}
}
return false;
};办法 2. 哈希表
- 思路：循环数组，将元素存入 set，判断每个元素是否存在于 set 中
- 复杂度：工夫复杂度
O(n)，空间复杂度O(n)
js：
var containsDuplicate = function(nums) {const set = new Set();
for (const x of nums) {if (set.has(x)) {return true;}
set.add(x);
}
return false;
};905. 按奇偶排序数组 (easy)
给你一个整数数组 nums，将 nums 中的的所有偶数元素挪动到数组的后面，后跟所有奇数元素。
返回满足此条件的 任一数组 作为答案。
示例 1：
输出：nums = [3,1,2,4]
输入：[2,4,3,1]
解释：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。
示例 2：输出：nums = [0]
输入：[0]提醒：
1 <= nums.length <= 5000
0 <= nums[i] <= 5000
办法 1. 排序
- 思路：排序比拟，偶数在前，奇数在后
- 复杂度：工夫复杂度
O(nlogn)，空间复杂度O(logn)，排序额定的空间
js：
var sortArrayByParity = function(A) {return A.sort((a, b) => (a & 1) - (b & 1))
};办法 2. 双指针
- 思路：右指针从右往左，直到遇到第一个偶数，左指针从左往右，直到遇到第一个奇数，而后替换地位
- 复杂度：工夫复杂度
O(n)，空间复杂度O(1)
js:
var sortArrayByParity = function(A, l = 0, r = A.length - 1) {while(l !== r) {while (r > 0 && A[r] & 1) r--
while (l < r && (A[l] & 1) === 0) l++
[A[l], A[r]] = [A[r], A[l]]
}
return A
};75. 色彩分类（medium）
给定一个蕴含红色、红色和蓝色、共 n 个元素的数组 nums，原地对它们进行排序，使得雷同色彩的元素相邻，并依照红色、红色、蓝色顺序排列。
咱们应用整数 0、1 和 2 别离示意红色、红色和蓝色。
必须在不应用库的 sort 函数的状况下解决这个问题。
示例 1：
输出：nums = [2,0,2,1,1,0]
输入：[0,0,1,1,2,2]
示例 2：输出：nums = [2,0,1]
输入：[0,1,2]提醒：
n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2进阶：
你能够不应用代码库中的排序函数来解决这道题吗？
你能想出一个仅应用常数空间的一趟扫描算法吗？
动画过大，点击查看
办法 1. 双指针
-
思路：筹备 p0，p1 两个指针，p0 指向 0 元素，p1 指向 1，初始化的时候，两个指针都指向数组的第一个地位。而后循环数组
- 遇见 1 就替换以后元素和 p1，让 p1 加 1，向前挪动一位
- 遇见 0 就替换以后元素和 p0，如果 p1 小于 p0，则此时 p0 指向的元素是 1，与 i 地位元素替换之后 这个替换过来的 1 地位就不对了，所以替换过来的 1 须要在和 p1 替换一下，这时 p0 和 p1 都指向了正确的元素，所以都须要向前挪动一次。如果 p0 等于 p1，则后面的元素都是 0，所以 p0 和 p1 也要向前挪动一次
- 复杂度：工夫复杂度
O(n)，n 是数组的长度，空间简单O(1)
js：
var sortColors = function (nums) {
let p0 = 0 // 指向 0
let p1 = 0 // 指向 0
for (let i = 0; i < nums.length; i++) {if (nums[i] === 1) {// 如果以后 i 指向的元素等于 1，则替换以后元素和 p1 指向的元素
let temp = nums[p1]
nums[p1] = nums[i]
nums[i] = temp
p1++
} else if (nums[i] === 0) {// 如果以后 i 指向的元素等于 0，则替换以后元素和 p0 指向的元素
let temp = nums[p0]
nums[p0] = nums[i]
nums[i] = temp
// 如果 p0 小于 p1 则此时 p0 指向的元素是 1，与 i 地位元素替换之后 这个替换过来的 1 地位就不对了 所以替换过来的 1 须要在和 p1 替换一下
if (p0 < p1) {temp = nums[i];
nums[i] = nums[p1];
nums[p1] = temp;
}
// 每次替换 0 之后都要挪动 p0 和 p1，如果 p0===p1，则后面都是 0，如果 p0<p1, 后面的代码曾经替换了两次
p0++
p1++
}
}
};办法 2. 双指针
-
思路：筹备两指针，p0 指向元素 0，它右边的都是 0，p2 指向 2，它左边都是 2，而后循环数组，当循环到了 p2，阐明 p2 左边的元素都是正确的数，所以
i<=p2- 如果此时 i 指向元素 2 i 小于 p2 则一直替换 p2 和 i 指向的元素 因为替换过去的数可能还是 2，那这个 2 就处于不正确的地位了
- 如果此时 i 指向元素 0 则替换 p0 和 i 指向的元素
- 循环实现则 0 和 2 都拍好了，两头的 1 天然也是正确的地位
- 复杂度：工夫复杂度
O(n)，n 是数组的长度，空间简单O(1)
js：
var sortColors = function (nums) {
let p0 = 0;// 指向 0
let p2 = nums.length - 1;// 指向 2
for (let i = 0; i <= p2; i++) {// 当循环到了 p2 阐明 p2 左边的元素都是正确的数，所以 i <=p2
// 如果此时 i 指向元素 2 i 小于 p2 则一直替换 p2 和 i 指向的元素 因为替换过去的数可能还是 2，那这个 2 就处于不正确的地位了
while (nums[i] === 2 && i < p2) {let temp = nums[i];
nums[i] = nums[p2];
nums[p2] = temp;
p2--;
}
// 如果此时 i 指向元素 0 则替换 p0 和 i 指向的元素
if (nums[i] === 0) {let temp = nums[i];
nums[i] = nums[p0];
nums[p0] = temp;
p0++;
}
}
};
// 写法 2
var sortColors = function (nums) {const swap = (list, p1, p2) => [list[p1], list[p2]] = [list[p2], list[p1]]
let red = 0,
blue = nums.length - 1,
p = 0
while (p <= blue) {switch (nums[p]) {
case 0:
swap(nums, red++, p)
p++
break;
case 1:// 遇见 1 始终让 p ++ 这样即便替换过去的是 2 也是处于正确的地位
p++
break;
case 2:
swap(nums, blue--, p)
break;
default:
break;
}
}
};283. 挪动零 (easy)
给定一个数组 nums，编写一个函数将所有 0 挪动到数组的开端，同时放弃非零元素的绝对程序。
请留神，必须在不复制数组的状况下原地对数组进行操作。
示例 1:
输出: nums = [0,1,0,3,12]
输入: [1,3,12,0,0]
示例 2:输出: nums = [0]
输入: [0]提醒:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 – 1进阶：你能尽量减少实现的操作次数吗？
动画过大，点击查看
办法 1: 两次遍历
- 思路：遍历数组，定义索引 j 为数组的第一个地位，遇上非 0 元素，让 j 地位上的元素等于这个非 0 元素，遍历完数组之后，j 地位之后的元素全副置为 0
- 复杂度：工夫复杂度
O(n)，空间复杂度O(1)
js：
var moveZeroes = function (nums) {
let j = 0;
for (let i = 0; i < nums.length; i++) {if (nums[i] !== 0) {// 遇到非 0 元素，让 nums[j] = nums[i]，而后 j ++
nums[j] = nums[i];
j++;
}
}
for (let i = j; i < nums.length; i++) {// 剩下的元素全是 0
nums[i] = 0;
}
return nums;
};办法 2: 双指针一次遍历
- 思路：定义 left、right 指针，right 从左往右挪动，遇上非 0 元素，替换 left 和 right 对应的元素，替换之后
left++ - 复杂度：工夫复杂度
O(n)，空间复杂度O(1)
js：
var moveZeroes = function(nums) {
let left=0,right=0
while(right<nums.length){if(nums[right]!==0){// 遇上非 0 元素，替换 left 和 right 对应的元素
swap(nums,left,right)
left++// 替换之后 left++
}
right++
}
};
function swap(nums,l,r){let temp=nums[r]
nums[r]=nums[l]
nums[l]=temp
}350. 两个数组的交加 II（easy）
给你两个整数数组 nums1 和 nums2，请你以数组模式返回两数组的交加。返回后果中每个元素呈现的次数，应与元素在两个数组中都呈现的次数统一（如果呈现次数不统一，则思考取较小值）。能够不思考输入后果的程序。
示例 1：
输出：nums1 = [1,2,2,1], nums2 = [2,2]
输入：[2,2]
示例 2:输出：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输入：[4,9]提醒：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000进阶：
如果给定的数组曾经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小，哪种办法更优？
如果 nums2 的元素存储在磁盘上，内存是无限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
办法 1: 哈希表
- 思路：统计 nums1 中各个元素的频次，循环 nums2，看 nums2 中的元素是否在 mums1 频数哈希表中存在，存在的话退出后果，并且频数减 1
- 复杂度：工夫复杂度
O(m+n)，遍历两个数组，哈希表操作复杂度是O(1)。空间复杂度O(min(m,n))对长度小的数组进行哈希。
js：
const intersect = (nums1, nums2) => {const map = {};
const res = [];
if (nums1.length < nums2.length) {[nums1, nums2] = [nums2, nums1]
}
for (const num1 of nums1) {//nums1 中各个元素的频次
if (map[num1]) {map[num1]++;
} else {map[num1] = 1;
}
}
for (const num2 of nums2) { // 遍历 nums2
const val = map[num2];
if (val > 0) { // 在 nums1 中
res.push(num2); // 退出 res 数组
map[num2]--; // 匹配掉一个，就减一个
}
}
return res;
};办法 2: 双指针
- 思路：p1，p2 双指针指向两数组中的元素，在 p1，p2 都不越界的状况下开始循环，如果 p1 指向的元素大，挪动 p2，如果 p2 指向的元素大，挪动 p1，遇到雷同则退出入 res，挪动两指针
- 复杂度：工夫复杂度
O(mlogm+nlogn)，m、n 别离是数组的长度，排序工夫复杂度是O(mlogm+nlogn)，两数组遍历是O(m+n)。空间复杂度O(logm+logn)
js：
const intersect = (nums1, nums2) => {nums1.sort((a, b) => a - b);
nums2.sort((a, b) => a - b); // 排序两个数组
const res = [];
let p1 = 0;// 指向 nums1 中的元素
let p2 = 0;// 指向 nums2 中的元素
while (p1 < nums1.length && p2 < nums2.length) {// 不越界条件
if (nums1[p1] > nums2[p2]) {//p1 指向的元素大，挪动 p2
p2++;
} else if (nums1[p1] < nums2[p2]) {//p2 指向的元素大，挪动 p1
p1++;
} else {
// 遇到雷同则退出入 res，挪动两指针
res.push(nums1[p1]);
p1++;
p2++;
}
}
return res;
};238. 除本身以外数组的乘积 (medium)
给你一个整数数组 nums，返回 数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
题目数据 保障 数组 nums 之中任意元素的全副前缀元素和后缀的乘积都在 32 位 整数范畴内。
请不要应用除法，且在 O(n) 工夫复杂度内实现此题。
示例 1:
输出: nums = [1,2,3,4]
输入: [24,12,8,6]
示例 2:输出: nums = [-1,1,0,-3,3]
输入: [0,0,9,0,0]提醒：
2 <= nums.length <= 105
-30 <= nums[i] <= 30
保障 数组 nums 之中任意元素的全副前缀元素和后缀的乘积都在 32 位 整数范畴内进阶：你能够在 O(1) 的额定空间复杂度内实现这个题目吗？（出于对空间复杂度剖析的目标，输入数组不被视为额定空间。）
- 思路：从左往右遍历，记录从左到以后地位前一位的乘积，而后从右往左遍历，从左到以后地位前一位的乘积乘上左边元素的积。
- 复杂度：工夫复杂度
O(n)，空间复杂度O(1)
js：
var productExceptSelf = function (nums) {const res = [];
res[0] = 1;
// 从左往右遍历
// 记录从左到以后地位前一位的乘积
for (let i = 1; i < nums.length; i++) {res[i] = res[i - 1] * nums[i - 1];
}
let right = 1;
// 从右往左遍历
// 从左到以后地位前一位的乘积 乘上 左边元素的积
for (let j = nums.length - 1; j >= 0; j--) {res[j] *= right;
right *= nums[j];
}
return res;
};209. 长度最小的子数组 (medium)
给定一个含有 n 个正整数的数组和一个正整数 target。
找出该数组中满足其和 ≥ target 的长度最小的 间断子数组 [numsl, numsl+1, …, numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例 1：
输出：target = 7, nums = [2,3,1,2,4,3]
输入：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：输出：target = 4, nums = [1,4,4]
输入：1
示例 3：输出：target = 11, nums = [1,1,1,1,1,1,1,1]
输入：0提醒：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
办法 1: 滑动窗口
动画过大，点击查看
- 思路：左右指针是滑动窗口的两边，用滑动窗口循环数组，不断扩大窗口，如果窗口中元素的和大于 target，就开始放大窗口，而后更新最小滑动窗口
- 复杂度：工夫复杂度
O(n)，数组中的元素都遍历一次，空间复杂度O(1)
js：
var minSubArrayLen = function(target, nums) {
const len = nums.length;
let l = r = sum = 0,
res = len + 1; // 最大的窗口不会超过本身长度
while(r < len) {sum += nums[r++];// 扩充窗口
while(sum >= target) {
res = res < r - l ? res : r - l;// 更新最小值
sum-=nums[l++];// 放大窗口
}
}
return res > len ? 0 : res;
};922. 按奇偶排序数组 II（easy）
给定一个非负整数数组 nums，nums 中一半整数是 奇数，一半整数是 偶数。
对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数；当 nums[i] 为偶数时，i 也是 偶数。
你能够返回 任何满足上述条件的数组作为答案。
示例 1：
输出：nums = [4,2,5,7]
输入：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被承受。
示例 2：输出：nums = [2,3]
输入：[2,3]提醒：
2 <= nums.length <= 2 * 104
nums.length 是偶数
nums 中一半是偶数
0 <= nums[i] <= 1000进阶：能够不应用额定空间解决问题吗？
办法 1. 双指针
- 思路：循环偶数地位 如果遇到了奇数，而后循环奇数地位 如果遇到了第一个偶数，就交位
- 复杂度：工夫复杂度
O(n)，空间复杂度O(1)
js：
const swap = (nums, i, j) => {const temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
};
var sortArrayByParityII = function(nums) {
const n = nums.length;
let j = 1;
for (let i = 0; i < n; i += 2) {if (nums[i] & 1) {// 循环偶数地位 如果遇到了奇数
while (nums[j] & 1) {// 循环奇数地位 如果遇到了第一个偶数
j += 2;
}
swap(nums, i, j);// 交地位换
}
}
return nums;
};视频解说：传送门