hot100之两数之和

总结leetcode hot100系列开始，用python刷

1.字典，使用hash缩短查找target-num的速度，时间、空间复杂度均为O（n）

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record_dict = dict()
        for index, num in enumerate(nums):
            if target - num in record_dict:
                return [record_dict[target - num], index]
            record_dict[num] = index

2.先排序再滑动窗口，时间复杂度为O(nlogn)、空间复杂度为O（n）

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record_dict = dict()
        for index, num in enumerate(nums):
            record_dict[str(index)] = num    
        sorted_dict = sorted(record_dict.items(), key=lambda index: index[1])
        right, left = 0, len(nums) - 1
        while right < left:
            if sorted_dict[right][1] + sorted_dict[left][1] == target:
                return [int(sorted_dict[right][0]), int(sorted_dict[left][0])]
            elif sorted_dict[right][1] + sorted_dict[left][1] > target:
                left -= 1
            else:
                right += 1

原文地址：https://blog.csdn.net/m0_72806612/article/details/145245026

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！