[leetcode] No 1. Two Sum Python Solution

00_coding_study

[leetcode] No 1. Two Sum Python Solution

for dream 2023. 5. 6. 19:43

[Problem]

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.

[Explanation]

There are given array and a target value.

In the array, two values that can make the target value by adding should be found.

Then, the found value will be return as index.

[Solution]

There is a follow-up question. To make lower complexity, hash algorithm has to be used.

Hash table is an algorithm to save some values as keys.

There are two tries.

But, two tries' concepts are the same.

First, find the value that is calculated by subtracting nums from target.

In order to check wheter the value is in the hash table or not.

If there is, return answer.

Second, the nums is saved in the hash table.

(1) Using list

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

        for i in range(len_nums):
            r = target - nums[i]
            r_h = abs(r % len_nums)

            while(True):
                if hash_table[r_h] == -1: break

                r_idx = hash_table[r_h]
                if nums[r_idx] == r and i != r_idx:
                    return [i, r_idx]

                r_h = (r_h + 1) % len_nums

            h = abs(nums[i] % len_nums)

            while(True):
                if hash_table[h] == -1:
                    hash_table[h] = i
                    break
                h = (h + 1) % len_nums

(2) Using dictionary

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        len_nums = len(nums)
        hash_table = {}

        for i in range(len_nums):
            r = target - nums[i]

            if r in hash_table:
                return [i, hash_table[r]]

            h = nums[i]
            hash_table[h] = i

Well, using dictionary looks like more simpler and runtime is a little better.

However, I don't know how memory cah be reduced..hh