Leetcode 두 합계

Question

저는 현재 파이썬 배경에서 오는 C ++를 배우고 있으므로 다음 문제 설명에 대해 파이썬과 C ++에 솔루션을 포함 할 것입니다.

정수 nums의 배열과 정수 대상이 주어지면 대상에 합산되도록 두 숫자의 인덱스를 반환합니다. 각 입력에 정확히 하나의 솔루션이 있다고 가정 할 수 있으며 동일한 요소를 두 번 사용할 수 없습니다. 어떤 순서로든 답변을 반환 할 수 있습니다.

예 1 :

입력 : nums = [2,7,11,15], target = 9

출력 : [0,1]

예 2 :

입력 : nums = [3,2,4], target = 6

출력 : [1,2]

귀하의 의견 / 성능 개선 제안 / 기타 제안을 듣고 싶습니다. 여기에 링크가 있습니다

two_sum.py

def two_sum(nums: list, target: int):
    for i, n in enumerate(nums):
        match = target - n
        if match in (rest := nums[i + 1:]):
            match_at = rest.index(match)
            return i, match_at + i + 1


if __name__ == '__main__':
    if result := two_sum([2, 7, 11, 15], 22):
        print(f'Indices:\n{result}')
    else:
        print('No matches found')

Leetcode 통계 :

런타임 : 772ms, Two Sum에 대한 Python 온라인 제출의 36.98 %보다 빠릅니다. 메모리 사용량 : 14.4MB, Two Sum에 대한 Python 온라인 제출의 49.82 % 미만.

two_sum.h

#ifndef LEETCODE_TWO_SUM_H
#define LEETCODE_TWO_SUM_H
#include <iostream>
#include <vector>
using std::vector;
using std::cout;
using std::endl;


vector<int> two_sum_solution(vector<int> &nums, int target) {
    vector <int> results;
    for (int i = 0; i < nums.size(); ++i) {
        int match = target - nums[i];
        for (int j = i + 1; j < nums.size(); ++j) {
            if (nums[j] == match) {
                for (int index_match : {
                            i, j
                        })
                    results.push_back(index_match);
            }

        }
    }
    return results;
}
#endif //LEETCODE_TWO_SUM_H

main.cpp

#include <vector>
#include "two_sum.h"
using std::vector;


int main() {
    vector<int> v1{2, 7, 11, 15};
    vector<int> v = two_sum_solution(v1, 22);
    if (!v.empty()) {
        cout << "Indices:" << endl;
        for (auto i: v)
            cout << i << " ";
    }
    else (cout << "No matches found");
}

Leetcode 통계 :

런타임 : 384ms, Two Sum에 대한 C ++ 온라인 제출의 34.03 %보다 빠릅니다. 메모리 사용량 : 9.3MB, Two Sum에 대한 C ++ 온라인 제출의 12.99 % 미만.

Answer 1

저는 C ++ 전문가는 아니지만 Python 솔루션에 대한 피드백을 줄 수 있습니다.

현재 솔루션은 \$O(n^2)\$. 기본적으로, 각 번호를 n입력의 nums발견 target - n에서 nums. 그것을 개선하는 방법?

알고리즘의 두 번째 부분은 \$O(n)\$에 \$O(1)\$. target - n목록에서 찾는 대신 사전을 사용할 수 있습니다.

def two_sum(nums: list, target: int):
    num_index = {}
    for i, n in enumerate(nums):
        match = target - n
        if match in num_index:
            return num_index[match], i
        num_index[n] = i
    return -1

결과 :

Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB

Answer 2

필요한 헤더 파일 만 포함하십시오.

당신의에서 two_sum.h파일, 당신은 필요가 없습니다 iostream당신이 그 기능 중 하나를 사용하지 않는 때문에. 그 기억 #include그대로 복사하여 붙여 넣습니다 파일을 여러 파일에서이 헤더 파일을 포함하고 있습니다 그렇다면, 그것은 잠재적으로 컴파일 시간이 느려질 수 있습니다.

분할 선언 및 정의

일반적으로 파일을 헤더 파일 (일반적으로 *.h, *.hpp, *.hh)과 소스 파일 (일반적으로)의 두 부분으로 분할합니다 *.cpp, *.cc. 헤더 파일은 선언으로 만 구성되고 소스 파일에는 구현이 포함됩니다.

따라서 귀하의 경우 헤더 파일은 다음과 같습니다.

two_sum.h

#ifndef LEETCODE_TWO_SUM_H
#define LEETCODE_TWO_SUM_H

#include <vector>

std::vector<int> two_sum_solution(std::vector<int> &nums, int target);

#endif // LEETCODE_TWO_SUM_H

소스 파일은 다음과 같습니다.

two_sum.cpp

#include "two_sum.h"
std::vector<int> two_sum_solution(std::vector<int> &nums, int target)
{
     ...
}

실제로 two_sum.h(구현과 함께) 여러 파일 에 포함하려고 하면 One-Definition Rule을 위반하게 됩니다. 소스 파일에는 동일한 기능에 대한 여러 정의가 포함되어 있으며 링커에서 오류가 발생합니다. 돌아 다니는 한 가지 방법은 함수를 표시하는 inline것이지만 전자를 사용하고 싶을 가능성이 큽니다.

using namespace헤더 파일에 없음

using namespace헤더 파일에서 또는 그 변형을 하지 마십시오 . 헤더 파일은 여러 소스 파일에 복사되어 붙여 넣기 때문에 성가신 오류가 발생할 수 있습니다. 여길 봐

const 참조 사용

이후 two_sum_solution개질되지 않은 nums벡터를 CONST 참조를 전달한다.

size_t 대 배열 인덱스의 int

배열 인덱스에 int 대신 size_t 사용을 고려하십시오.

auto최대한 많이 사용

코드에는 auto유형을 지정하는 대신 사용할 수있는 몇 가지 인스턴스가 있습니다 . 예 :

auto match = target - nums[i]; auto v = two_sum_solution(v1, 22);

가장 안쪽의 고리는 무의미합니다

간단하게

results.push_back(i);
results.push_back(j);

또한 솔루션을 찾으면 즉시 결과를 반환 할 수 있습니다.

Answer 3

주어진 배열에 대한 첫 번째 반복에서 값-> 인덱스의 맵을 만들어 성능을 향상시킬 수 있습니다.

현재 프로그램은 다음을 수행합니다 (시간 복잡성).

1. index, value배열의 모든 쌍을 반복 합니다 ( \$ O(n) \$)
2. target - value배열에서 검색 ( \$ O(n) \$)
3. 의 룩업 인덱스 target - value( \$ O(n) \$)

그리고 이것들은 모두 중첩 되었기 때문에 \$ O(n^2) \$( \$ n^3 \$ 각 반복에 대해 마지막 조회가 수행되지 않기 때문에).

---

내가 제안한 솔루션 :

1. 지도 / 딕셔너리 만들기 {value: index}( \$ O(n) \$)
2. index, value어레이 반복 ( \$ O(n) \$)
3. 맵 / 딕셔너리에서 조회 및 반환 인덱스 ( \$ O(1) \$)

---

def two_sum(numbers: list[int], target: int):
    lookup: dict = {
        value: index
        for index, value in enumerate(numbers)
    }
    for index, value in enumerate(numbers):
        match = target - value
        if search_index := lookup.get(match):
            return index, search_index
    return None

Answer 4

제가 C 배경에서 왔고 지난 몇 년 동안 작업에 Python을 사용하기 시작했기 때문에 이것은 저에게 흥미로 웠습니다. 그래서 저는 당신과 반대 경로를 가졌습니다. Python을 시작했을 때 목록을 반복하는 것이 매우 명확하고 명확하기 때문에 귀하와 같은 솔루션을 매우 선호했습니다.

그러나 나는 직장에서 더 능숙한 파이썬 프로그래머가 표준 라이브러리를 사용할 때 내 코드를 더 잘 이해한다는 것을 배웠습니다. 이러한 도구를 배우는 데 투자하기 시작하자 1) 내 코드를 더 간결하게 만들고 2) 시간 및 / 또는 공간에서 더 효율적이라는 두 가지 효과가있었습니다.

이 경우 패키지 combinations에서 문제를 해결할 것입니다 itertools.

from itertools import combinations

def two_sum(nums, target):
    pairs_with_indices = combinations(enumerate(nums), 2)

    # result is a generator comprehension.
    winning_pairs = ((index_i, index_j)
                     for (index_i, i), (index_j, j) in pairs_with_indices
                     if sum((i, j)) == target)

    # Insert as much error checking as you need...
    return next(winning_pairs)

Numpy를 사용하는 훨씬 더 간결하고 명확한 솔루션이있을 것입니다. Numpy는 제 작업 라인 (데이터 과학)의 효과적인 표준 라이브러리이지만 모든 곳에서 사실이 아닙니다.

코드와 다른 점은 하나만있는 오류의 여지가 없다는 것입니다. 내 경험상 다음과 같은 코드

if match in (rest := nums[i + 1:]):
        match_at = rest.index(match)
        return i, match_at + i + 1

쓰기가 쉽고 읽기가 어렵고 유지 관리가 쉬운 것에서 불가능한 것까지 전체 갬빗에 걸쳐 있습니다. 다시 말해, 파이썬에서 수동으로 인덱스를 관리하는 것은 나에게 매달릴 수있는 충분한 로프를 제공하며 표준 라이브러리 함수는 훌륭한 대안이었습니다.

Answer 5

컨테이너 파악

std::unordered_map이 문제에서 당신의 친구입니다. 이전에 숫자를 본 적이 없을 때마다 operator[]또는 insert함수를 사용 하여 숫자와 색인을 추가하십시오. 를 사용 find하면 key-value쌍인 반복자를 반환합니다 .

예 : auto location = m.find(numToFind);

location->first당신의 열쇠이고 location->second당신의 가치입니다

돌아올 때 push_back을 사용하지 마십시오.

다음과 같은 이니셜 라이저 목록을 간단히 반환 할 수 있습니다 {i,j}..