LeetCode 算法题
1. Two Sum 两数之和
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
1 | class Solution: |
一遍哈希表:
在进行迭代并将元素插入到表中的同时,我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在,那我们已经找到了对应解,并立即将其返回。
复杂度分析:
时间复杂度:\(O(n) \) , 我们只遍历了包含有 \(n\) 个元素的列表一次。在表中进行的每次查找只花费 \(O(1)\) 的时间。
空间复杂度: \(O(n)\) , 所需的额外空间取决于哈希表中存储的元素数量,该表最多需要存储 \(n\) 个元素。
2. Add Two Numbers 两数相加
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
1 | class ListNode: |
3. Longest Substring Without Repeating Characters 最长无重复字符的子串
给定一个字符串,找出不含有重复字符的最长子串的长度。
示例:
给定
"abcabcbb"
,没有重复字符的最长子串是"abc"
,那么长度就是3。给定
"bbbbb"
,最长的子串就是"b"
,长度是1。给定
"pwwkew"
,最长子串是"wke"
,长度是3。请注意答案必须是一个子串,"pwke"
是 _子序列 _而不是子串。
1 | class Solution(object): |