手写算法: 三数之和

15. 三数之和

思路

• 判断数组的长度，小于 3，直接 return []

• 排序数组，对于相同的元素在一块连续的内存中方便后续去重

• 遍历数组，拿到固定一个数作为此轮的基准数 nums[i]

• 判断第一个数是否大于 0,若是大于 0 那证明之后的值肯定也是大于 0,肯定不符合三数之和。

• 去重，相同的数跳过

• 再用左右指针分别指向 nums[i]的两端，L = i + 1, R = len - 1。半判断这三个数 相加是否等于 0

在填充到 result 后，同样需要去重，判断 L 与 L+1 的值，相等的话结果会重复需跳过。R 也同样需要去重

• 若 sum ＜ 0 ，L++

• 若 sum ＞ 0， R-－

时间复杂度：O(n^2)

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  const len = nums.length;
  let result = [];
  if (len < 3) return result;
  nums.sort((a, b) => a - b);
  for (let i = 0; i < len; i++) {
    if (nums[i] > 0) break;
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let L = i + 1;
    let R = len - 1;
    while (L < R) {
      let sum = nums[i] + nums[L] + nums[R];
      if (sum === 0) {
        result.push([nums[i], nums[L], nums[R]]);
        while (L < R && nums[L] === nums[L + 1]) L++;
        while (L < R && nums[R] === nums[R - 1]) R--;
        L++;
        R--;
      } else if (sum < 0) {
        L++;
      } else if (sum > 0) {
        R--;
      }
    }
  }
  return result;
};

手写题: 移动 0 到最后

168. 移动 0 到最后

思路

双指针

1. index 表示将要被替换的 0 的下标，i 表示当前不为 0 的下标

2. 当 list[i]等于 0 的时候，指针会一直往后移，直到找到不为 0 的元素，跟之前为 0 的元素(list[index])进行调换

3. 调换完后，index++，因为调换完后该位置不为 0 了，所以指针往右移动

时间复杂度:0(n)， 空间复杂度: 0(1)

/**
 * @param {Array<any>} list
 * @returns {void}
 */
function moveZeros(list) {
  let index = 0;
  for (let i = 0; i < list.length; i++) {
    if (list[i] !== 0) {
      [list[index], list[i]] = [list[i], list[index]];
      index += 1;
    }
  }
}