[LeetCode] 1. Two Sum

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

內容目錄

Easy

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:

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

Example 2:

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

Example 3:

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

Constraints:

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

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

Python

				
					from typing import List

# brute force
# time complexity: O(n^2)
# space complexity: O(1)

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

# hashMap
# time complexity: O(n)
# space complexity: O(1)

class Solution(object):
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numMap = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in numMap:
                return [numMap[complement], i]
            numMap[num] = i
        return []


# two pointer
# time complexity: O(n)
# space complexity: O(1)

class Solution(object):
   def twoSum(self, nums: List[int], target: int) -> List[List[int]]:
       res = []
       left, right = 0, len(nums) - 1
       while (left < right):
           currSum = nums[left] + nums[right]
           if currSum < target or (left > 0 and nums[left] == nums[left - 1]):
               left += 1
           elif currSum > target or (right < len(nums)-1 and nums[right] == nums[right + 1]):
               right -= 1
           else:
               res.append([nums[left], nums[right]])
               left += 1
               right -= 1
       return res


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

solution = Solution()
result = solution.twoSum(nums, target)

print(result)

Easy

Python

相關文章