两数相加、长度最小的子数组、移动零

两数相加

题目描述

给定两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例

例图 1

输入：l1 = [2, 4, 3], l2 = [5, 6, 4]

输出：[7, 0, 8]

解释：342 + 465 = 807

题解

ts
function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  let flag = 0,
    head = new ListNode(),
    p = head;

  while (l1 || l2 || flag) {
    const num1 = l1 ? l1.val : 0,
      num2 = l2 ? l2.val : 0;
    const cur = num1 + num2 + flag;

    flag = Math.floor(cur / 10);
    p.next = new ListNode(cur % 10);

    p = p.next;
    if (l1) {
      l1 = l1.next;
    }
    if (l2) {
      l2 = l2.next;
    }
  }

  return head.next;
}

长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target。

找出该数组中满足其总和大于等于 target 的长度最小的子数组 [nums[l], nums[l+1], ..., nums[r-1], nums[r]] ，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：target = 7, nums = [2,3,1,2,4,3]

输出：2

解释：子数组 [4, 3] 是该条件下的长度最小的子数组。

思路

使用滑动窗口。

用 start 表示窗口的左边界，end 表示右边界
每次将 nums[end] 加入当前窗口的和 sum
如果 sum >= target，就尝试收缩左边界 start，这个阶段同时需要更新最小长度。直到不满足条件为止

注意

不要排序。因为题中是连续的子数组，是有顺序的
看清楚是和大于等于 target 的，不是单纯的等于

题解

ts
function minSubArrayLen(target: number, nums: number[]): number {
  let n = nums.length;
  let minLen = Infinity;
  let sum = 0;
  let start = 0;

  for (let end = 0; end < n; end++) {
    sum += nums[end];

    // 尽量缩小窗口直到 sum < target
    while (sum >= target) {
      minLen = Math.min(minLen, end - start + 1);
      sum -= nums[start];
      start++;
    }
  }

  return minLen === Infinity ? 0 : minLen;
}

移动零

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

示例:

输入: nums = [0,1,0,3,12]

输出: [1,3,12,0,0]

思路

双指针题型。

相当于把所有非零元素全部去掉，再在剩下的位置统一填充 0

题解

ts
function moveZeroes(nums: number[]): void {
  const solution = () => {
    let fast = 0,
      slow = 0;
    while (fast < nums.length) {
      if (nums[fast] !== 0) {
        nums[slow] = nums[fast];
        slow++;
      }
      fast++;
    }

    return slow;
  };

  const start = solution();

  for (let i = start; i < nums.length; i++) {
    nums[i] = 0;
  }
}