Hướng dẫn two sum leetcode solution python github - hai tổng leetcode giải pháp python github

Hai tổng

https://leetcode.com/problems/two-sum/description/

Đưa ra một loạt các số nguyên, trả lại các chỉ số của hai số sao cho chúng cộng vào một mục tiêu Spiecific.

Bạn có thể cho rằng mỗi đầu vào woo chính xác một giải pháp và bạn không được sử dụng phần tử nói hai lần.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Giải pháp của tôi:

1. Thời gian: O (n^2), không gian: O (1)

Sử dụng giải pháp bạo lực để chu kỳ mảng. Nhưng nó sẽ báo cáo nhiều hơn thời gian quy định. Do đó, Python không nên thực hiện bạo lực.

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(0, len(nums)-1):
          for j in range(i + 1, len(nums)):
            if(nums[i] + nums[j] == target):
              return [i, j]

Tối ưu hóa chương trình, chúng tôi sử dụng chức năng chỉ mục trong danh sách để giảm thời gian tìm kiếm thích hợp

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i, n in enumerate(nums):
            if((target - n) in nums[i+1:]):
                return [i, nums[i+1:].index(target-n) + i + 1]

Thời gian để lấy 936 ms

2. Thời gian: O (n), không gian (n)

Thiết lập bảng băm để tạo điều kiện cho các chỉ mục và giảm thời gian tìm kiếm. Ở đây chúng tôi sử dụng từ điển để thực hiện

_

class Solution:
   def twoSum(self, nums, target):
       """
       :type nums: List[int]
       :type target: int
       :rtype: List[int]
       """
       nums_dict = {};
       for i, n in enumerate(nums):
           if((target - n) in nums_dict.keys()):
               return [nums_dict[target - n], i]
           nums_dict[n] = i      

Thời gian mất 40 ms (tốt hơn 97,27%)

Do đó, câu hỏi này có thể được coi là một trường hợp hy sinh sự phức tạp không gian để đổi lấy sự phức tạp về thời gian.