[Leetcode] two sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

1
2
3

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

1 2	Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3:

1 2	Input: nums = [3,3], target = 6 Output: [0,1]

Constraints:

\(2 \leq \text{nums.length} \leq 10^4\)
\(-10^9 \leq \text{nums[i]} \leq 10^9\)
\(-10^9 \leq \text{target} \leq 10^9\)
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than \(O(n^2)\) time complexity?

Approach 1: Brute Force

Algorithm

The brute force approach is simple. Loop through each element \(x\) and find if there is another value that equals to target−\(x\)

Implementation

from __future__ import annotations

class Solution:
    # brute-force two sums solutions
    def two_sum(self, nums: list[int], target: int) -> list[int]:
        '''
        Return indices i, j such that nums[i] + nums[j] == target.
        Args:
            nums: List of integers to search.
            target: The sum we want two elements of nums to add up to.

        Returns:
            A list with two indices [i, j]. Order does not matter.

        Note:
            LeetCode guarantees exactly one valid answer.
        '''
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[j] == target - nums[i]:
                    return [i,j]
        return []
    
def main() -> None:
    sol= Solution()
    print(sol.two_sum([2, 7, 11, 15], 9))
    print(sol.two_sum([3, 2, 4], 6)) 
    print(sol.two_sum([3, 3], 6))

if __name__ == "__main__":
    main()

Complexity Analysis

Time complexity: \(O(n^2)\). For each element, we try to find its complement by looping through the rest of the array which takes \(O(n)\) time. Therefore, the time complexity is \(O(n^2)\).
Space complexity: \(O(1)\). The space required does not depend on the size of the input array, so only constant space is used.

Notes

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ...

from typing import List imports the List type for type hints. (on Python 3.9+, we can write list[int] and skip this import.)

class Solution: calls code as Solution().twoSum(...). So the function to live inside a class named Solution.

def twoSum(self, nums: List[int], target: int) -> List[int]: defines a method named twoSum.

self is the instance of Solution. We don’t use it here; it’s just the method signature.
nums: List[int] is a type hint: “nums should be a list of integers”.
target: int means “target should be an integer”.
-> List[int] means “this function returns a list of integers” (the two indices).
Type hints don’t change runtime behavior; they help readers and tools.

Type annotations && method

Here, we provide a detailed explanation of type annotations and methods.

[[leetcode-1-1-two-sum-type-annotation]]

Conventions

instance

As for the instance, it doesn’t have to be named self, but we should name it self (and cls for class methods). That’s the Python convention (PEP 8), and most linters/IDEs expect it. e.g.

from __future__ import annotations
from dataclasses import dataclass

@dataclass
class User:
    name: str

    @classmethod
    def from_first_last(cls, first: str, last: str) -> User:
        """Alternate constructor that returns cls(...), not hard-coded User(...)."""
        return cls(name=f"{first} {last}")

u = User.from_first_last("Ada", "Lovelace")  # calls on the class; receives cls=User

Notes

§a. from dataclasses import dataclass

dataclasses is a standard library module (a Python file bundled with Python, introduced in 3.7).
dataclass is not a class; it’s a function (a decorator) defined inside the dataclasses module. We import that function with this line so we can write @dataclass above a class.

So:

dataclasses → module (a namespace of things)
dataclass → a decorator function provided by that module

§b. What does @dataclass do? What does @ mean?

@something above a function or class is decorator syntax sugar. This:

1 2	@decorator def f(): ...

is equivalent to:

1 2	def f(): ... f = decorator(f)

Same for classes:

@decorator
class C: ...
# is the same as:
class C: ...
C = decorator(C)

§c. What @dataclass specifically does

@dataclass takes our class definition and returns a modified class with a bunch of boilerplate auto-generated based on our annotated attributes:

__init__ (constructor)
__repr__ (nice string representation)
__eq__ (equality by fields)
optional ordering methods (__lt__, …) if we pass order=True
optional immutability if we pass frozen=True
slots if we pass slots=True (Py3.10+)

Example:

from dataclasses import dataclass

@dataclass
class Point:
    x: float
    y: float

p = Point(3.0, 4.0)
print(p)           # Point(x=3.0, y=4.0)
print(p.x, p.y)    # 3.0 4.0

Without @dataclass, we’d have to manually write __init__, __repr__, __eq__, etc.

A slightly fancier variant:

from dataclasses import dataclass

@dataclass(order=True, frozen=True)
class Card:
    rank: int
    suit: str

# order=True -> cards can be compared/sorted by (rank, suit)
# frozen=True -> instances are immutable

§d. What does @classmethod do?

Same decorator idea: @classmethod transforms a function defined inside a class into a class method.

An instance method (normal def method(self, ...)) receives the instance as its first argument (self).
A class method receives the class as its first argument (cls) instead—so it can operate on class-level data, construct new instances, or behave polymorphically with subclasses.

Example: alternate constructor

class User:
    def __init__(self, name: str) -> None:
        self.name = name

    @classmethod
    def from_first_last(cls, first: str, last: str) -> "User":
        # cls is the actual class we called on (User or a subclass)
        return cls(f"{first} {last}")

u = User.from_first_last("Ada", "Lovelace")

Example: class-level state

class Counter:
    count: int = 0  # class variable (shared by all instances)

    def bump(self) -> None:
        type(self).count += 1  # or self.__class__.count += 1

    @classmethod
    def reset(cls) -> None:
        cls.count = 0

Counter.reset()
c1, c2 = Counter(), Counter()
c1.bump(); c2.bump()
print(Counter.count)  # 2

§e. When to use which?

Use @dataclass when we want Python to generate boilerplate methods for a data-holding class.
Use @classmethod when a method should work with the class itself (cls) rather than a specific instance (self)—e.g., alternate constructors or class-wide configuration.
The @ just means “apply this decorator to the thing below.”

decorators

A decorator is just a callable that takes a function and returns a new one, often a wrapper, letting us extend behavior while keeping functions clean and following the Open–Closed Principle.

[[leetcode-1-1-two-sum-type-decorators]]