Two sum - javascript

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

기록. Brute force

일단 for iteration 을 사용해서 brute force way 로 더해가면서 목표 target 값에 도달하려는 의도는 확실.

이제 문제를 읽고, 예시를 보니 알 수있는 사실이 있다. 바로 '어떻게든 해당 nums array 의 0, 1 위치에 있는 값을 비교해서 더해봤을 때 목표 값이 9가 나오면 '참(true)' 이다. 라는 걸 증명해내는 코드를 구성해라는 의미인 것.

 

그래서 가장 확실하게 이해할 수 있는 형태가 바로 brute force 방식으로 접근 해 보는 것 이었다.

 

- 저 아래의 코드에서, i = 0 란, (아까 그 output 에서도 보이던 그 0, 1 중) 0번째 초기 array element에서 brute force 로 시작해서 올라(right side order)간다는 의미이고.

- let j = i + 1 이란, 그 초기값 i 에서 + 1 칸의 element (in array) 만큼 앞서 나가서 i++ 씩 right side order로 진행 해 가며 비교하겠다는 의미.

 

이렇게 선언이 다 되었으니,

이제 해당 배열값이 담긴 nums 에 해당 구성을 대입하면 nums[i] 가 나오며 이는 j 도 이하동문.

 

그렇게, nums[i], nums[j] 까지는 구상이 가능했었다. 하지만 그 다음은 도대체 어쩔까?

일단 둘을 더한 값을 출력 해야 할 텐데. 여기에서 고민을 하던 중,

'by comparing the data of nums array to whatever target value, and if both side found as identical value...' 

였다.

 

그리고 비교해 본 결과, 

const twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return [i, j]
            }
        }
    }
};

for iteration 또는 for loops 라고 알려진 이 방식은 한국어로는 for 반복문으로 알려져 있다. 

Python "for" Loops (Definite Iteration) – Real Python

참, 그래서 Big o notation 으로 정의(?) 를 내리면 이건 어떨까?

O(n^2) 가 아닐까 싶다. 근거는 저 2개의 for iteration 으로서, 총 two times 가 진행 되었으니.

 

Extra.

http://thomas-johnson.net/2019/12/13/time-and-space/

Considering Time Complexity with Two Sum · Thomas Johnson