Leetcode算法题笔记

Leetcode 题目列表

【题面】给定整数数组和目标值，找出数组里的两个数，使得他们的和等于目标值。

【思路一】遍历数组里的每个元素，寻找能与之相加得到目标值的另一个元素。时间复杂度是O(n^2)。空间复杂度O(1)。

【思路二】先将数组按从小到大排序，然后用指针p、q分别指向首、尾元素，p向尾部前进，q向首部前进。省略取值运算符*，并记目标值为t，按以下步骤计算。

如果 p+q = t，得到一组结果，p、q分别与自己前进方向的元素作差，差值较小者前进一步；

如果 p+q > t，q前进一步；

如果 p+q < t，p前进一步。

如果p、q相遇，计算结束。

时间复杂度是 O(nlogn) + O(n) = O(nlogn)。空间复杂度O(1)。

【思路三】构造哈希表，再查询。时间复杂度O(n)，空间复杂度O(n)。

【题面】多位整数的每一位数字反向存在链表里（比如 587 存储结构为 7->8->5 ），计算两个这种链表的和，并输出新链表。

【思路一】p,q 分别指向两链表的头节点，用一个变量 f 记是否进位。p、q同步前进，求和（p+q+f），把值同时存在p和q中（因为不知道哪个比较长），并更新进位标志f。假设链表长度不一样，那么短的先停止计算。若此时进位标志为1，则继续计算较长链表。如果最后溢出的话，新增节点。

时间复杂度O(max(m,n))，空间复杂度O(1)

【思路二】如果不破坏原来的链表，则时间复杂度O(max(m,n))，空间复杂度O(max(m,n))。