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개 밖에 없다고 가정하겠습니다.

に答える


巡視
  • が並んでいます.
  • インデックスが
  • より大きい要素;
  • targetの場合は
  • indexを配列に入れる
  • を返します.
    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;
    }