Skip to main content
Fix method signature
Source Link
Marc
  • 5.7k
  • 2
  • 14
  • 35

I am not an expert in C++ but I can give a feedback about the Python solution.

Your current solution runs in \$O(n^2)\$. Basically, for each number n of the input nums, find target - n in nums. How to improved it?

The second part of the algorithm can be improved from \$O(n)\$ to \$O(1)\$. Instead of looking up target - n in a list, you can use a dictionary:

def twoSumtwo_sum(self, nums: List[int]list, target: int) -> List[int]:
    num_index = {}
    for i, n in enumerate(nums):
        match = target - n
        if match in num_index:
            return num_index[match], i
        num_index[n] = i
    return -1

Results:

Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB

I am not an expert in C++ but I can give a feedback about the Python solution.

Your current solution runs in \$O(n^2)\$. Basically, for each number n of the input nums, find target - n in nums. How to improved it?

The second part of the algorithm can be improved from \$O(n)\$ to \$O(1)\$. Instead of looking up target - n in a list, you can use a dictionary:

def twoSum(self, nums: List[int], target: int) -> List[int]:
    num_index = {}
    for i, n in enumerate(nums):
        match = target - n
        if match in num_index:
            return num_index[match], i
        num_index[n] = i
    return -1

Results:

Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB

I am not an expert in C++ but I can give a feedback about the Python solution.

Your current solution runs in \$O(n^2)\$. Basically, for each number n of the input nums, find target - n in nums. How to improved it?

The second part of the algorithm can be improved from \$O(n)\$ to \$O(1)\$. Instead of looking up target - n in a list, you can use a dictionary:

def two_sum(nums: list, target: int):
    num_index = {}
    for i, n in enumerate(nums):
        match = target - n
        if match in num_index:
            return num_index[match], i
        num_index[n] = i
    return -1

Results:

Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB
added 53 characters in body
Source Link
Marc
  • 5.7k
  • 2
  • 14
  • 35

I am not an expert in C++ but I can give a feedback about the Python solution.

Your current solution runs in \$O(n^2)\$. Basically, for each number n of the input nums, find target - n in nums. How to improved it?

The second part of the algorithm can be improved from \$O(n)\$ to \$O(1)\$ by using. Instead of looking up target - n in a list, you can use a dictionary:

def twoSum(self, nums: List[int], target: int) -> List[int]:
    num_index = {}
    for i, n in enumerate(nums):
        match = target - n
        if match in num_index:
            return num_index[match], i
        num_index[n] = i
    return -1

Results:

Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB

I am not expert in C++ but I can give a feedback about the Python solution.

Your current solution runs in \$O(n^2)\$. Basically, for each number n of the input nums, find target - n in nums. How to improved it?

The second part of the algorithm can be improved from \$O(n)\$ to \$O(1)\$ by using a dictionary:

def twoSum(self, nums: List[int], target: int) -> List[int]:
    num_index = {}
    for i, n in enumerate(nums):
        match = target - n
        if match in num_index:
            return num_index[match], i
        num_index[n] = i
    return -1

Results:

Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB

I am not an expert in C++ but I can give a feedback about the Python solution.

Your current solution runs in \$O(n^2)\$. Basically, for each number n of the input nums, find target - n in nums. How to improved it?

The second part of the algorithm can be improved from \$O(n)\$ to \$O(1)\$. Instead of looking up target - n in a list, you can use a dictionary:

def twoSum(self, nums: List[int], target: int) -> List[int]:
    num_index = {}
    for i, n in enumerate(nums):
        match = target - n
        if match in num_index:
            return num_index[match], i
        num_index[n] = i
    return -1

Results:

Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB
Source Link
Marc
  • 5.7k
  • 2
  • 14
  • 35

I am not expert in C++ but I can give a feedback about the Python solution.

Your current solution runs in \$O(n^2)\$. Basically, for each number n of the input nums, find target - n in nums. How to improved it?

The second part of the algorithm can be improved from \$O(n)\$ to \$O(1)\$ by using a dictionary:

def twoSum(self, nums: List[int], target: int) -> List[int]:
    num_index = {}
    for i, n in enumerate(nums):
        match = target - n
        if match in num_index:
            return num_index[match], i
        num_index[n] = i
    return -1

Results:

Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB