LeetCode 第一周

1
from typing import List
2

3

4
class Solution:
5
    def twoSum(self, nums: List[int], target: int) -> List[int]:
6
        """
7
        枚举数组中所有不同的元素组合，找到和为 target 的两个元素。
8

9
        时间复杂度：O(n²)
10
        空间复杂度：O(1)
11
        """
12

13
        # 第一个下标的范围是 0 到 len(nums) - 2
14
        for first_index in range(len(nums) - 1):
15

16
            # 从 first_index 的后一位开始，避免：
17
            # 1. 重复使用同一个元素
18
            # 2. 重复检查相同的元素组合
19
            for second_index in range(first_index + 1, len(nums)):
20

21
                # 如果两个元素之和等于目标值，则返回它们的下标
22
                if nums[first_index] + nums[second_index] == target:
23
                    return [first_index, second_index]
24

25
        # 根据题目条件，每组输入一定存在答案。
26
        # 保留空列表返回值，可以使函数在其他情况下也有明确返回值。
27
        return []

1
from typing import List
2

3

4
class Solution:
5
    def twoSum(self, nums: List[int], target: int) -> List[int]:
6
        """
7
        使用哈希表记录已经遍历过的数字及其下标。
8

9
        对于当前数字 num，计算：
10
            complement = target - num
11

12
        如果 complement 已经出现过，说明：
13
            complement + num == target
14

15
        时间复杂度：O(n)
16
        空间复杂度：O(n)
17
        """
18

19
        # 用于保存“数字: 下标”
20
        # 例如 {2: 0} 表示数字 2 出现在下标 0
21
        num_to_index = {}
22

23
        # enumerate() 同时提供当前元素的下标和值
24
        for current_index, current_num in enumerate(nums):
25

26
            # 计算与当前数字相加后能够得到 target 的补数
27
            complement = target - current_num
28

29
            # 如果补数之前出现过，直接返回补数和当前数字的下标
30
            if complement in num_to_index:
31
                return [num_to_index[complement], current_index]
32

33
            # 当前没有找到答案，将当前数字及其下标保存起来，
34
            # 供后面的元素查询
35
            num_to_index[current_num] = current_index
36

37
        # 根据题目条件，每组输入一定存在答案
38
        return []

1
# class ListNode:
2
#     def __init__(self, val=0, next=None):
3
#         self.val = val
4
#         self.next = next
5

6
class Solution:
7
    def addTwoNumbers(self, l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
8
        current1 = l1
9
        current2 = l2
10

11
        dummy = ListNode()
12
        tail = dummy
13

14
        carry = 0
15

16
        while current1 is not None or current2 is not None or carry != 0:
17
            # 如果链表已经结束，将该位置看作0
18
            value1 = current1.val if current1 is not None else 0
19
            value2 = current2.val if current2 is not None else 0
20

21
            # 计算当前位数的数字（包括进位）
22
            total = value1 + value2 + carry
23

24
            # 取得当前位。总值大于等于 10 时，只保留个位
25
            current_digit = total % 10
26

27
            # 得到进位数字
28
            carry = total // 10
29

30
            # 将最终结果插入链表，指针进入下一位
31
            tail.next = ListNode(current_digit)
32
            tail = tail.next
33

34
            # 输入链表尚未结束时，才移动对应指针
35
            if current1 is not None:
36
                current1 = current1.next
37

38
            if current2 is not None:
39
                current2 = current2.next
40

41
        # 得到结果链表
42
        return dummy.next
43

44
        # 以下为本地测试的打印环境，无需将其复制到 leetcode 中
45
        # result_head = dummy.next
46

47
        # current = result_head
48

49
        # while current is not None:
50
        #     print(current.val)
51
        #     current = current.next

1
def study(s):
2
    characters = set()
3
    left = 0
4
    max_length = 0
5

6
    for right in range(len(s)):
7

8
        # 如果右侧的新字符已经在窗口中出现重复
9
        # 就不断从窗口左侧移除字符
10
        while s[right] in characters:
11
            characters.remove(s[left])
12
            left += 1
13

14
        # 重复已经消失，将当前字符加入窗口
15
        characters.add(s[right])
16

17
        # 根据 left 和 right 计算当前窗口长度
18
        current_length = right - left + 1
19

20
        # 比较当前长度和历史最大长度
21
        max_length = max(max_length, current_length)
22

23
    return max_length