有序的数组，试试用指针法遍历
最近在看数据结构和算法，努力总结出道~
TL:DR
指针的本质，是记住数组遍历的进度，从而减少无效遍历的范围。
当遍历有序的数组的时候，因为有序，所以更大更小的值已经确定，可以用指针法记住数组遍历的进度，从而减少无效遍历的范围
数组上，单个指针的话，先将指针指向开始(或末尾)，然后指针移动，当移动到数组之外，就表示数组遍历完毕。
数组上，两个指针的话，如果出现在两端，随着两边指针移动，未遍历中间的元素范围就慢慢变小，直到指针相邻或者重合表示，遍历完毕，也叫对撞指针法。
遇到求和或者比大小问题的时候，如果数组是无序的，可以尝试有序之后再使用指针法。
练习：有序数组合并
网络异常，图片无法展示
|
我看到的第一想法是sort大法：
var merge = function (nums1, m, nums2, n) { // num1里面多余的元素删掉，并且将num2里面的元素插入到num1里面 nums1.splice(m,n,...nums2.slice(0,n)) // 排序 nums1.sort((a,b)=>a-b) };
splice方法一定要会，可删，可增。第一个索引表示要操作的位置（这个位置的元素肯定要变），第二个表示删除后面几个，之后的都表示插入的元素。
但其实，既然已经有序，就要充分利用这个条件，减少无效遍历。上指针大法！
本题，因为是num1够长，因为后面的空间是空的，所以从后面开始利用，节省空间。
- nums1、nums2本身有序，所以里面的数也是从小到大排列，也就是最大的数始终在末尾
- 将大的数，倒插进num1就好
- 一个指针，指向num1的最后一个数的位置。一个指向num2的最后一个数的位置。还用个指针指向填充到num1的哪个位置了
- 只要指针还在，就一直比较，前两个指针的数，大的往后填，且指针移动
- 指针1小于0的时候，表示num1遍历完了，那直接将num2里面，未遍历的数挨个直接塞到num1里就好
- 指针2小于0的时候，表示num2遍历完了，那就不用管了，数都在num1里面了
var merge = function (nums1, m, nums2, n) { // 指针初始都在末尾 let pointer1 = m - 1; let pointer2 = n - 1; let fillPointer = m + n - 1; // 一直遍历，直到有一个数组遍历完，一个数组遍历完的表现就是：pointer1 <0 || pointer2 <0 while (pointer1 >= 0 && pointer2 >= 0) { // num1指针的指向的值更大的话，就填充此值，然后移动指针，表示此值之后不再需要遍历了 if (nums1[pointer1] >= nums2[pointer2]) { nums1[fillPointer] = nums1[pointer1]; pointer1--; fillPointer--; } else { // 同理 nums1[fillPointer] = nums2[pointer2]; pointer2--; fillPointer--; } } // 当nums1先遍历完的时候，将nums2里面未遍历的值，插入到nums1即可 if (pointer1 < 0) { // pointer2 >=0是遍历的条件，一旦小于0就表示遍历完了 while (pointer2 >=0) { nums1[newPointer] = nums2[pointer2]; pointer2--; newPointer--; } } };
显然空间O(1)，时间O(m+n)
可以看下官方视频
练习：三数求和
网络异常，图片无法展示
|
暴力法，我就不说了，三重遍历，合适的组合丢出来就行，时间复杂度O(n^3)。
显然，这不是想要的过程。
两数求和，用Map，以空间换时间。 但三数求和，不固定的数有两个，是不适合用Map的，这里数组和求和，联想下指针。
指针的前提条件是有序的数组，所以这里先排序，然后使用指针法
- 数组先排序
- 固定一个数nums[i]，再使用左右指针指向 nums[i]后面的两端
- 判断三数之和，大于0右指针后退，小于0左指针前进，等于0保存索引且左右指针都动
- nums[i]如果大于0，则停止遍历，因为之后的肯定更大于0
- 对于重复的问题：左右指针以及i，只要和前面的值一致则跳过。
var threeSum = function (nums) { // nums = Array.from(new Set(nums)); nums.sort((a, b) => a - b); let res = []; let len = nums.length; // i是固定的第一个数的指针 for (let i = 0; i < len - 2; i++) { if (nums[i] > 0) { break; } // 相等就跳过，因为有i-1所以前面必须判断i>0，不然会报错 if (i > 0 && nums[i] === nums[i - 1]) { continue; } // L是左指针 let L = i + 1; // R是右指针 let R = len - 1; // 当L>=R的时候，表示数组遍历完了 while (L < R) { const sum = nums[L] + nums[R] + nums[i]; // 大于0，右指针后退 if (sum > 0) { // 这句是去重复的。值相同的话，跳过，这里注意必须加L<R，不然R--，是有可能小于L的，这不是我们想要的 while (L < R && nums[R] === nums[R - 1]) R--; R--; } else if (sum < 0) { while (L < R && nums[L] === nums[L + 1]) L++; L++; } else { res.push([nums[i], nums[L], nums[R]]); while (L < R && nums[L] === nums[L + 1]) L++; L++; while (L < R && nums[R] === nums[R - 1]) R--; R--; } } } return res; };
时间复杂度降成O(n^2)。
可以看下官方视频
