1. Two Sum 两数之和

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:  
def twoSum(self,nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
#用len()方法取得nums列表长度
n = len(nums)
#创建一个空字典
d = {}
for x in range(n):
a = target - nums[x]
#字典d中存在nums[x]时
if nums[x] in d:
return d[nums[x]],x
#否则往字典增加键/值对
else:
d[a] = x
#边往字典增加键/值对,边与nums[x]进行对比

一遍哈希表:

在进行迭代并将元素插入到表中的同时,我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在,那我们已经找到了对应解,并立即将其返回。

复杂度分析:

  • 时间复杂度:\(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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class ListNode:
def __init__(self, x):
self.val = x
self.next = None

class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
a = 0
temp = ListNode(0)
l3 = temp

while l1 != None or l2 != None or a != 0:
if l1 != None:
a += l1.val
l1 = l1.next
if l2 != None:
a += l2.val
l2 = l2.next
temp.next = ListNode(a%10)
temp = temp.next
a = a//10
#l3代替temp来输出链表
return l3.next

3. Longest Substring Without Repeating Characters 最长无重复字符的子串

给定一个字符串,找出不含有重复字符的最长子串的长度。

示例:

给定 "abcabcbb" ,没有重复字符的最长子串是 "abc" ,那么长度就是3。

给定 "bbbbb" ,最长的子串就是 "b" ,长度是1。

给定 "pwwkew" ,最长子串是 "wke" ,长度是3。请注意答案必须是一个子串"pwke" 是 _子序列 _而不是子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def lengthOfLongestSubstring(self, s):
left = 0
ans = 0
last = {}
# left用于记录合法的左边界位置,last用于记录字符上一次出现的位置

for i in range(len(s)):
# 子串中出现重复字符,变更left至上一次s[i]出现位置之后,使得子串合法
if s[i] in last and last[s[i]] >= left:
left = last[s[i]] + 1
else:
ans = max(ans, i-left+1) # 这一行代码放在else里比放在else外(不要else) 块25%
last[s[i]] = i

return ans