每日一题——Python代码实现力扣1. 两数之和（举一反三+思想解读+逐步优化）五千字好文

一个认为一切根源都是“自己不够强”的INTJ

个人主页：用哲学编程-CSDN博客
专栏：每日一题——举一反三
Python编程学习
Python内置函数

Python-3.12.0文档解读

菜鸡写法

代码分析

时间复杂度分析

空间复杂度分析

改进建议

我要更强

方法1: 使用哈希表（字典）

方法2: 排序和双指针

方法3: 使用集合（仅适用于特殊情况）

哲学和编程思想

1. 空间与时间的权衡（Space-Time Tradeoff）

2. 分治法（Divide and Conquer）

3. 迭代与递归

4. 数据结构的选择

5. 算法优化

6. 抽象与具体化

7. 代码的可读性与效率

举一反三

1. 空间与时间的权衡

2. 分治法

3. 迭代与递归

4. 数据结构的选择

5. 算法优化

6. 抽象与具体化

7. 代码的可读性与效率

题目链接：https://leetcode.cn/problems/two-sum/description/

菜鸡写法

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        len_nums=len(nums)
        for i in range(len_nums):
            for j in range(len_nums):
                if i==j:
                    continue
                if nums[i]+nums[j]==target:
                    return [i,j]

这段代码是一个Python类Solution的方法twoSum，其目的是在给定的整数列表nums中找到两个数，使得这两个数的和等于给定的目标值target。如果找到这样的两个数，方法返回一个包含这两个数索引的列表；如果没有找到，理论上应该返回一个特定的值（如None或[-1, -1]），但这段代码在找到解后立即返回，没有处理无解的情况。

代码分析

循环结构：代码使用了两个嵌套的循环来遍历列表nums。外层循环从第一个元素遍历到最后一个元素，内层循环同样从第一个元素遍历到最后一个元素。
条件判断：在内层循环中，首先通过if i==j来跳过自身与自身相加的情况，然后通过if nums[i]+nums[j]==target来检查两个数的和是否等于目标值。
返回结果：一旦找到满足条件的两个数，立即返回它们的索引。

时间复杂度分析

由于使用了两个嵌套的循环，每个循环都遍历整个列表，因此时间复杂度为O(n^2)，其中n是列表nums的长度。这是因为对于列表中的每一个元素，都需要与其他所有元素进行比较。

空间复杂度分析

空间复杂度为O(1)，因为除了输入的列表和几个变量（如索引和循环控制变量）外，没有使用额外的数据结构来存储信息。所有的操作都是基于原始列表进行的。

改进建议

这段代码的时间复杂度较高，可以通过使用哈希表（在Python中为字典）来优化。使用哈希表可以在一次遍历中找到解，时间复杂度可以降低到O(n)。

我要更强

方法1: 使用哈希表（字典）

这是最常见的优化方法，通过使用哈希表来存储元素及其索引，可以在一次遍历中找到解。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_to_index = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_to_index:
                return [num_to_index[complement], i]
            num_to_index[num] = i
        return None  # 如果没有找到，返回None

时间复杂度: O(n)，其中n是列表nums的长度。我们只遍历了一次列表。空间复杂度: O(n)，因为我们需要一个哈希表来存储元素及其索引。

方法2: 排序和双指针

这种方法首先对数组进行排序，然后使用两个指针分别从头部和尾部开始移动，直到找到解。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        sorted_indices = sorted(range(len(nums)), key=lambda x: nums[x])
        left, right = 0, len(nums) - 1
        while left < right:
            sum_ = nums[sorted_indices[left]] + nums[sorted_indices[right]]
            if sum_ == target:
                return [sorted_indices[left], sorted_indices[right]]
            elif sum_ < target:
                left += 1
            else:
                right -= 1
        return None  # 如果没有找到，返回None

时间复杂度: O(n log n)，主要来自于排序操作。空间复杂度: O(n)，因为我们需要一个额外的列表来存储排序后的索引。

方法3: 使用集合（仅适用于特殊情况）

如果数组中的数字都是正数且范围有限，我们可以使用集合来存储所有可能的差值，然后检查这些差值是否存在于数组中。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        if all(isinstance(num, int) and num >= 0 for num in nums):
            possible_diffs = set()
            for num in nums:
                if num in possible_diffs:
                    return [target - num, num]
                possible_diffs.add(target - num)
        return None  # 如果没有找到，返回None

时间复杂度: O(n)，遍历了一次数组。空间复杂度: O(n)，因为需要一个集合来存储所有可能的差值。

这些方法提供了不同的优化策略，可以根据具体问题的要求和限制选择最合适的方法。