算法练习day101、除了自身以外的数组的乘积问题除自身以外数组的乘积。给定一个整数数组nums返回一个数组answer其中answer[i]等于nums中除nums[i]之外其余各元素的乘积。题目要求不能使用除法时间复杂度 O(n)空间复杂度 O(1)输出数组不计入空间复杂度解题思路核心思路是使用前缀积和后缀积。我们可以通过两次遍历来完成第一次遍历从左到右计算每个位置左侧所有元素的乘积存入answer数组。第二次遍历从右到左用一个变量right记录当前位置右侧所有元素的乘积然后与answer[i]相乘得到最终结果。代码实现const productExceptSelf function (nums) { const len nums.length const answer new Array(len) // 左乘积answer[i]存i左边所有乘积 answer[0] 1 for (let i 1; i len; i) { answer[i] answer[i - 1] * nums[i - 1] } let right 1 // right 保存右边乘积从后往前遍历 for (let i len - 1; i 0; i--) { answer[i] * right right * nums[i] } return answer }复杂度分析时间复杂度O(n)其中 n 是数组长度。我们只进行了两次遍历。空间复杂度O(1)除了输出数组外只使用了常数空间。2、相交链表问题给你两个单链表的头节点headA和headB请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回null。题目要求时间复杂度 O(mn)其中 m 和 n 分别是链表 A 和 B 的长度空间复杂度 O(1)不能修改链表结构解题思路核心思路是使用双指针法让两个指针分别遍历两个链表当走到链表末尾时切换到另一个链表的头部继续遍历。如果两个链表相交那么两个指针最终会在相交节点相遇如果不相交两个指针最终都会走到null。具体算法初始化两个指针pA和pB分别指向链表 A 和链表 B 的头节点同时向前移动两个指针当pA到达链表 A 的末尾时将其重定位到链表 B 的头节点当pB到达链表 B 的末尾时将其重定位到链表 A 的头节点如果两个链表相交pA和pB最终会在相交节点相遇如果不相交两个指针最终都会到达null为什么这样能工作设链表 A 的非公共部分长度为 a链表 B 的非公共部分长度为 b公共部分长度为 c指针pA走过的路径a c b指针pB走过的路径b c a两者路径长度相等所以如果相交必然在相交节点相遇代码实现// Definition for singly-linked list class ListNode { constructor(val) { this.val val this.next null } } /** 寻找两个链表的相交节点 param {ListNode} headA param {ListNode} headB return {ListNode} */ var getIntersectionNode function(headA, headB) { if (!headA || !headB) return null let pA headA let pB headB // 双指针遍历 while (pA ! pB) { // 如果pA走到末尾切换到链表B头部 pA pA ? pA.next : headB // 如果pB走到末尾切换到链表A头部 pB pB ? pB.next : headA } // 返回相交节点或null return pA } // 测试用例构造相交链表 const a1 new ListNode(4) const a2 new ListNode(1) const c1 new ListNode(8) const c2 new ListNode(4) const c3 new ListNode(5) a1.next a2 a2.next c1 c1.next c2 c2.next c3 const b1 new ListNode(5) const b2 new ListNode(6) const b3 new ListNode(1) b1.next b2 b2.next b3 b3.next c1 // B链表接到c1交点是c1(val8) // 测试 const result getIntersectionNode(a1, b1) console.log(相交节点值:, result ? result.val : null) // 输出: 8复杂度分析时间复杂度O(mn)其中 m 和 n 分别是链表 A 和 B 的长度。每个指针最多遍历 mn 个节点。空间复杂度O(1)只使用了两个指针变量没有使用额外的数据结构。边界情况两个链表都为空返回null一个链表为空返回null两个链表不相交最终两个指针都指向null两个链表完全重合返回第一个节点相交节点在链表头部直接返回相交节点