-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTwoSum.py
More file actions
43 lines (42 loc) · 2.89 KB
/
TwoSum.py
File metadata and controls
43 lines (42 loc) · 2.89 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
########################################################################
# Source : <https://leetcode.com/problems/two-sum/> #
# Author : Rose Martin #
# Date : 20260408 #
#----------------------------------------------------------------------#
# Challenge Description - [1. 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: #
# Input: nums = [2,7,11,15], target = 9 #
# Output: [0,1] #
# Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]. #
# #
# Input: nums = [3,2,4], target = 6 #
# Output: [1,2] #
# #
# Input: nums = [3,3], target = 6 #
# Output: [0,1] #
#----------------------------------------------------------------------#
# Constraints: #
# - 2 <= nums.length <= 10^4 #
# - -10^9 <= nums[i] <= 10^9 #
# - -10^9 <= target <= 10^9 #
# - Only one valid answer exists. #
#----------------------------------------------------------------------#
# Note: #
# - Can you come up with an algorithm that is less than O(n^2) #
# time complexity? #
########################################################################
class Solution:
def twoSum(self, nums, target):
nums_hash = {} # Map number -> index
for i in range(len(nums)):
if target - nums[i] in nums_hash: # Check if complement exists
return [nums_hash[target - nums[i]], i] # Return both indices
nums_hash[nums[i]] = i # Store current number and index