【Leetcode刷题】算法：两数之和

痛定思痛。 2023-09-27 23:04 33阅读 0赞

#### 文章目录 ####

*  一、题目描述
 *  二、尝试1
 *  三、尝试2
 *  四、尝试3
 *  五、尝试4

## 一、题目描述 ##

![在这里插入图片描述][df1df2b9cc3b491c863ffc8800d114e4.png]

## 二、尝试1 ##

from typing import List
    class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            num_dict = {
        }
    
            for i in range(len(nums)):
                diff = target - nums[i]
    
                if diff in num_dict:
                    return [num_dict[diff], i]
    
                num_dict[nums[i]] = i
    
            return []

![在这里插入图片描述][a684b3cda7304a7ea68f74487abb26e9.png]

## 三、尝试2 ##

from typing import List
    
    class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            num_dict = {
        }
    
            for i, num in enumerate(nums):
                diff = target - num
                
                if diff in num_dict:
                    return [num_dict[diff], i]
                
                num_dict[num] = i
            
            return []

![在这里插入图片描述][c229f4e8a8b8456cab051b44641de8a4.png]

## 四、尝试3 ##

from typing import List
    
    class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            nums_sorted = sorted(enumerate(nums), key=lambda x: x[1])
            left, right = 0, len(nums) - 1
    
            while left < right:
                curr_sum = nums_sorted[left][1] + nums_sorted[right][1]
    
                if curr_sum == target:
                    return [nums_sorted[left][0], nums_sorted[right][0]]
    
                if curr_sum < target:
                    left += 1
                else:
                    right -= 1
    
            return []

![在这里插入图片描述][bcb2dacce0074e77bef56549fec4c65c.png]

## 五、尝试4 ##

class Solution:
        def twoSum(self, nums: List[int], target: int) -> List[int]:
            records = dict()
    
            # 用枚举更方便，就不需要通过索引再去取当前位置的值
            for idx, val in enumerate(nums):
                if target - val not in records:
                    records[val] = idx
                else:
                    return [records[target - val], idx]

![在这里插入图片描述][01f5238b0d634be28cd332822bbda54a.png]  
![在这里插入图片描述][bb0aa485b3104524b6f43286dd311236.png]  
![在这里插入图片描述][c2227d2e2d3b48a591eeca81f68c1f97.png]

[df1df2b9cc3b491c863ffc8800d114e4.png]: https://img-blog.csdnimg.cn/df1df2b9cc3b491c863ffc8800d114e4.png
[a684b3cda7304a7ea68f74487abb26e9.png]: https://img-blog.csdnimg.cn/a684b3cda7304a7ea68f74487abb26e9.png
[c229f4e8a8b8456cab051b44641de8a4.png]: https://img-blog.csdnimg.cn/c229f4e8a8b8456cab051b44641de8a4.png
[bcb2dacce0074e77bef56549fec4c65c.png]: https://img-blog.csdnimg.cn/bcb2dacce0074e77bef56549fec4c65c.png
[01f5238b0d634be28cd332822bbda54a.png]: https://img-blog.csdnimg.cn/01f5238b0d634be28cd332822bbda54a.png
[bb0aa485b3104524b6f43286dd311236.png]: https://img-blog.csdnimg.cn/bb0aa485b3104524b6f43286dd311236.png
[c2227d2e2d3b48a591eeca81f68c1f97.png]: https://img-blog.csdnimg.cn/c2227d2e2d3b48a591eeca81f68c1f97.png