0001.py

# Source: https://leetcode.com/problems/two-sum
# Title: Two Sum
# Difficulty: Easy
# Author: Mu Yang <http://muyang.pro>

################################################################################################################################
# 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^4
#   -10^9 <= nums[i] <= 10^9
#   -10^9 <= target <= 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?
#
################################################################################################################################

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

################################################################################################################################

class Solution2:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        idxs = sorted(range(len(nums)), key=lambda k: nums[k])
        i = 0
        j = len(nums)-1
        while True:
            s = nums[idxs[i]] + nums[idxs[j]]
            if s > target:
                j -= 1
            elif s < target:
                i += 1
            else:
                return [idxs[i], idxs[j]]