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

Two Sum

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

```
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. ** **

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.

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.

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.

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 ...

Recommended Posts