Code Kata_twoSum
8591 ワード
質問する
twoSum함수에 숫자배열과 '특정 수'를 인자로 넘기면,
더해서 '특정 수'가 나오는 index를 배열에 담아 return해 주세요.
nums: 숫자 배열
target: 두 수를 더해서 나올 수 있는 합계
return: 두 수의 index를 가진 숫자 배열
예를 들어,
nums: 숫자 배열
target: 두 수를 더해서 나올 수 있는 합계
return: 두 수의 index를 가진 숫자 배열
예를 들어,
nums은 [4, 9, 11, 14] target은 13
nums[0] + nums[1] = 4 + 9 = 13 이죠?
그러면 [0, 1]이 return 되어야 합니다.
# 가정
target으로 보내는 합계의 조합은 배열 전체 중에 2개 밖에 없다고 가정하겠습니다.
に答える
巡視
for(let i=0; i<nums.length-1; i++) {
for(let j=i+1; j<nums.length; j++) {
if(nums[i] + nums[j] === target) {
return [i, j];
}
}
}
ビオ記号法
アルゴリズムの効率を表し、通常、アルゴリズムの時間的複雑さと空間的複雑さを表すために使用される.アルゴリズムが最悪の場合に複雑さを測定する.定数項(ex|2 n中2)と無影響項(n^2+n中n)は無視される.なお、n個の変数に加えて、複数の変数がよく用いられる.
O(1)
//O(1)
(1+n)/2
//O(n)
const sum = 0;
for(i=1; i<=n; i++) {
sum = sum + i
}
//O(n^2): 보통 중첩된 반복문을 사용하는 알고리즘(일반적으로 좋지 않음)
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
}
}
bigoの表現によれば,我々のグループの解題は二重複文を用いたため,O(n^2)の時間的複雑さを持つ.時間内に二重複文を用いない解決策は考えられなかったが,チームメンバーはO(n)時間の複雑さの解決法を共有した.次回から時間の複雑さを考慮して、問題解決のために残ります.const container = {};
for (let i=0; i<nums.length; i++) {
const another = target - nums[i];
if (another in container) {
return [container[another], i];
}
container[nums[i]] = i;
}
Reference
この問題について(Code Kata_twoSum), 我々は、より多くの情報をここで見つけました https://velog.io/@dabin0219/Code-KatatwoSum작성중テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol