リートコード2合計
私は現在、Pythonのバックグラウンドからc ++を学んでいるので、次の問題ステートメントの解決策をpythonとc ++に含めます。
整数numsの配列と整数ターゲットが与えられた場合、それらがターゲットになるように2つの数値のインデックスを返します。各入力には正確に1つの解があると想定でき、同じ要素を2回使用することはできません。回答は任意の順序で返すことができます。
例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統計：
実行時間：772ミリ秒、Two SumのPythonオンライン送信の36.98％より高速。メモリ使用量：14.4 MB、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統計：
実行時間：384ミリ秒、Two SumのC ++オンライン送信の34.03％より高速。メモリ使用量：9.3 MB、TwoSumのC ++オンライン送信の12.99％未満。
回答
私はC ++の専門家ではありませんが、Pythonソリューションについてフィードバックを提供できます。
現在のソリューションは\で実行されます$O(n^2)\$。基本的には、各番号のn入力をnums、見つけるtarget - nの中でnums。それを改善する方法は？
アルゴリズムの2番目の部分は、\から改善できます。$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
必要なヘッダーファイルのみをインクルードします
あなたにはtwo_sum.h、ファイル、あなたは必要ありません。iostreamあなたはその機能のいずれかを使用していないことから、。#include文字通りファイルをコピーして貼り付けることを忘れないでください。したがって、このヘッダーファイルを複数のファイルにインクルードすると、コンパイル時間が遅くなる可能性があります。
分割宣言と定義
通常、ファイルはヘッダーファイル（通常はで終わる*.h, *.hpp, *.hh）とソースファイル（通常はで終わる*.cpp, *.cc）の2つの部分に分割します。ヘッダーファイルは宣言のみで構成され、ソースファイルには実装が含まれています。
したがって、あなたの場合、ヘッダーファイルは次のようになります。
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（実装とともに）を複数のファイルに含めようとすると、単一定義規則に違反することになります。ソースファイルには同じ関数の複数の定義が含まれているため、リンカはエラーを吐き出します。回避する1つの方法は、関数にマークを付ける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);
また、解決策を見つけたら、すぐに結果を返したい場合があります。
指定された配列の最初の反復で値のマップ->インデックスを作成することで、パフォーマンスを向上させることができます。
現在、プログラムは次のことを行います（時間計算量）。
index, value配列のすべてのペアを反復します（\$ O(n) \$）target - value配列内で検索（\$ O(n) \$）target - value（\のルックアップインデックス$ O(n) \$)
And since these are all nested, you get to \$ O(n^2) \$ (it isn't \$ n^3 \$ because last lookup is not being done for each iteration).
My proposed solution:
- Create a map/dict of
{value: index}(\$ O(n) \$) - Iterate over
index, valueof array (\$ O(n) \$) - Lookup and return index from the map/dict (\$ 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
This is interesting to me because I come from a C background and started using Python the past few years for work, so I've had the reverse path as you. When I started Python, I greatly preferred solutions like yours because looping through lists is so explicit and clear.
However, I since learned that more proficient Python programmers at work understand my code better when I use the standard library. Once I began to invest in learning those tools, it had the double effect of 1) making my code more succinct and 2) being more efficient in time and/or space.
In this case, I would solve the problem with combinations from the itertools package:
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)
There's probably an even better more succinct and clear solution using Numpy, which is effectively standard library in my line of work (data science) but that's not true everywhere.
One thing that's different than your code: there is no room for off-by-one-errors. In my experience, code like this
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
is easy for me to write, hard to read and maintainability spans the whole gambit from easy to impossible. In other words, managing indices manually in Python gives me just enough rope to hang myself with, and standard library functions have been a great alternative.
Know your containers
std::unordered_map is your friend in this problem. Whenever you've never previously seen a number, simply use the operator[] or insert function to add the number and its index. When using find, it will return an iterator, which is a key-value pair.
eg:
auto location = m.find(numToFind);
location->first is your key, and
location->second is your value
When you return, don't use push_back
You can simply return an initializer list like: {i,j}.