# Overview

I started Let Code to improve my programming skills. I will explain the basic problem TwoSum in Ruby.

Two Sum

## problem

Given an array of integers, returns an array of index combinations where the sum of the two elements is the target value.

## Example

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

Is given.

``````nums[0] + nums[1] = 2+7 = 9
``````

So

``````[0, 1]
``````

Returns.

** The goal is to write a method in Ruby that meets the above requirements. ** **

## Solution 1 [Brute Force]

Brute Force means "brute force" in Japanese. In other words, solve without thinking.

``````# @param {Integer[]}nums array of integers
# @param {Integer}target integer
# @return {Integer[]}Array of integers

def two_sum(nums, target)
(0..nums.length-1).each do |i|
(i+1..nums.length-1).each do |j|
return [i, j] if nums[i] + nums[j] == target #Check if it reaches the target value
end
end
end
``````

Based on one element, we will search for the elements after that to see if the sum becomes the target value.

Submitting this code will result in the following:

``````Runtime : 4656 ms(average)
Memory : 9.6 MB(average)
``````

The average is roughly above, but sometimes it's a time limit. (Out as a submission)

This is calculated by ʻeach` an average of n times x n-1 times, so the complexity order is indicated by * O * (\$ n ^ 2 \$). That is, the larger the number of elements, the more time is required as a quadratic function.

## Solution 2 [Two-pass Hash Table]

It is more efficient to look for the complement that is `target value-element 1` than to look for the element whose sum is the target value. Hashes are used there.

``````# @param {Integer[]}nums array of integers
# @param {Integer}target integer
# @return {Integer[]}Array of integers

def two_sum(nums, target)
hash = {}
(0..nums.length-1).each do |i|
hash.store(nums[i], i) #Initialize hash
end
(0..nums.length-1).each do |i|
complement = target - nums[i] #Prepare complement
return [i, hash.fetch(complement)] if hash.has_key?(complement) && hash.fetch(complement) != i #Complement check
end
end
``````

Prepare a hash in advance and search for the complement value stored.

By doing this, ʻeach` calculates n times x n-1 times only n times. Therefore, the complexity order is * O * (\$ n \$). And if you submit this code, the result will be:

``````Runtime : 43 ms(average)
Memory : 10.2 MB(average)
``````

It uses a little more memory, but it's horribly faster.

## Solution 3 [One-pass Hash Table]

This time there is also a technique using the same hash. It is completed in one scan.

``````# @param {Integer[]}nums array of integers
# @param {Integer}target integer
# @return {Integer[]}Array of integers

def two_sum(nums, target)
hash = {}
(0..nums.length-1).each do |i|
complement = target - nums[i]
return [hash.fetch(complement), i] if hash.has_key?(complement) #Complement check
hash.store(nums[i], i) #Added because the complement did not exist
end
``````

The amount of code has been reduced, but it is harder to read. This is a method to add elements when the elements that satisfy the conditions are not found. The amount of memory can be reduced a little because elements are added and searched in one scan. Similarly, the complexity order is * O * (\$ n \$), and the submission result is as follows.

``````Runtime : 48 ms(average)
Memory : 9.9 MB(average)
``````

It's a little slower, but it uses less memory. Which method is better than ** Solution 2 ** depends on the situation, I think it's clear how good the hash method is compared to ** Solution 1 **! Also, since the number of trials is 7 each, the accuracy of the average value is not high, but it is clear from this result.

# Summary

I explained Two Sum, which is the basic problem of Leet Code. We also found that the execution time can be significantly reduced by taking an appropriate solution. I think I learned a lot just by solving this one problem properly. I want to continue Let Code ...