有序的数组，试试用指针法遍历

最近在看数据结构和算法，努力总结出道~

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)。

可以看下官方视频

引用

• 修言的前端算法和数据结构