Leetcode dua jumlah
Saat ini saya mempelajari c ++ yang berasal dari latar belakang python, jadi saya akan menyertakan solusi di python dan di c ++ untuk pernyataan masalah berikut:
Diberikan array angka integer dan target integer, kembalikan indeks dari dua angka yang dijumlahkan menjadi target. Anda dapat berasumsi bahwa setiap masukan akan memiliki tepat satu solusi, dan Anda tidak boleh menggunakan elemen yang sama dua kali. Anda dapat mengembalikan jawabannya dalam urutan apa pun.
Contoh 1:
Masukan: jumlah = [2,7,11,15], target = 9
Keluaran: [0,1]
Contoh 2:
Masukan: jumlah = [3,2,4], target = 6
Keluaran: [1,2]
Saya ingin mendengar tanggapan / saran Anda untuk peningkatan kinerja / saran lainnya. Berikut tautannya
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')
Statistik Leetcode:
Durasi: 772 md, lebih cepat dari 36,98% pengiriman online Python untuk Two Sum. Penggunaan Memori: 14,4 MB, kurang dari 49,82% pengiriman online Python untuk Two Sum.
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");
}
Statistik Leetcode:
Durasi: 384 md, lebih cepat dari 34,03% pengiriman online C ++ untuk Two Sum. Penggunaan Memori: 9,3 MB, kurang dari 12,99% pengiriman online C ++ untuk Two Sum.
Jawaban
Saya bukan ahli dalam C ++ tetapi saya dapat memberikan umpan balik tentang solusi Python.
Solusi Anda saat ini berjalan di \$O(n^2)\$. Pada dasarnya, untuk setiap nomor nmasukan nums, temukan target - ndi nums. Bagaimana cara memperbaikinya?
Bagian kedua dari algoritme dapat ditingkatkan dari \$O(n)\$ke \$O(1)\$. Daripada mencari target - ndi daftar, Anda dapat menggunakan kamus:
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
Hasil:
Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB
Hanya sertakan file header yang Anda butuhkan
Di two_sum.hfile Anda, Anda tidak perlu iostream, karena Anda tidak menggunakan fungsinya. Ingatlah bahwa #includesecara harfiah salin-tempel file, jadi jika Anda memasukkan file header ini ke dalam banyak file, ini berpotensi memperlambat waktu kompilasi Anda.
Pisahkan deklarasi dan definisi
Biasanya, Anda akan membagi file Anda menjadi dua bagian: file header (biasanya diakhiri dengan *.h, *.hpp, *.hh) dan file sumber (biasanya diakhiri dengan *.cpp, *.cc). File header hanya terdiri dari deklarasi dan file sumber berisi implementasinya.
Jadi dalam kasus Anda, file header Anda akan terlihat seperti ini:
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
dan file sumber Anda akan terlihat seperti ini:
two_sum.cpp
#include "two_sum.h"
std::vector<int> two_sum_solution(std::vector<int> &nums, int target)
{
...
}
Faktanya, jika Anda mencoba memasukkan two_sum.h(dengan implementasi) ke dalam beberapa file, Anda akan melanggar Aturan Satu Definisi . File sumber Anda akan berisi beberapa definisi dari fungsi yang sama, dan linker akan mengeluarkan kesalahan. Salah satu cara untuk menyiasatinya adalah dengan menandai fungsinya inline, tetapi kemungkinan besar Anda ingin melakukan yang pertama.
Tidak ada using namespacedi file header
Jangan lakukan using namespaceatau variasinya di file header. Karena file header disalin ke seluruh file sumber, ini berpotensi menyebabkan kesalahan yang mengganggu. Lihat disini
Gunakan referensi const
Karena vektor two_sum_solutiontidak dimodifikasi nums, berikan dengan referensi const.
size_t vs int untuk indeks array
Pertimbangkan untuk menggunakan size_t daripada int untuk indeks array
Gunakan autosebanyak mungkin
Ada beberapa contoh dalam kode Anda di mana Anda dapat menggunakan autoalih-alih menentukan jenisnya. Contoh:
auto match = target - nums[i]; auto v = two_sum_solution(v1, 22);
Lingkaran paling dalam tidak ada gunanya
Lakukan saja
results.push_back(i);
results.push_back(j);
Juga, setelah Anda menemukan solusinya, Anda mungkin ingin segera mengembalikan hasilnya.
Anda mungkin dapat meningkatkan kinerja dengan membuat peta nilai -> indeks pada iterasi pertama di atas larik yang diberikan.
Saat ini, program Anda melakukan hal berikut (kompleksitas waktu):
- mengulangi semua
index, valuepasang larik ( \$ O(n) \$) - cari
target - valuedalam larik ( \$ O(n) \$) - indeks pencarian dari
target - value( \$ O(n) \$)
Dan karena ini semua bertingkat, Anda dapat \$ O(n^2) \$(bukan \$ n^3 \$ karena pencarian terakhir tidak dilakukan untuk setiap iterasi).
Solusi yang saya usulkan:
- Buat peta / dikt dari
{value: index}( \$ O(n) \$) - Iterasi di atas
index, valuelarik ( \$ O(n) \$) - Cari dan kembalikan indeks dari peta / 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
Ini menarik bagi saya karena saya berasal dari latar belakang C dan mulai menggunakan Python beberapa tahun terakhir untuk bekerja, jadi saya memiliki jalur sebaliknya seperti Anda. Ketika saya memulai Python, saya sangat menyukai solusi seperti milik Anda karena perulangan melalui daftar sangat eksplisit dan jelas.
Namun, saya mengetahui bahwa programmer Python yang lebih mahir di tempat kerja memahami kode saya dengan lebih baik ketika saya menggunakan pustaka standar. Begitu saya mulai berinvestasi dalam mempelajari alat-alat itu, itu memiliki efek ganda yaitu 1) membuat kode saya lebih ringkas dan 2) menjadi lebih efisien dalam waktu dan / atau ruang.
Dalam hal ini, saya akan menyelesaikan masalah dengan combinationsdari itertoolspaket:
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)
Mungkin ada solusi yang lebih ringkas dan jelas yang lebih baik menggunakan Numpy, yang merupakan pustaka standar yang efektif di bidang pekerjaan saya (ilmu data) tetapi itu tidak berlaku di semua tempat.
Satu hal yang berbeda dari kode Anda: tidak ada ruang untuk kesalahan off-by-one. Menurut pengalaman saya, kode seperti ini
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
mudah bagi saya untuk menulis, sulit untuk dibaca dan pemeliharaan mencakup keseluruhan langkah dari yang mudah hingga tidak mungkin. Dengan kata lain, mengelola indeks secara manual dengan Python memberi saya cukup tali untuk bertahan, dan fungsi pustaka standar telah menjadi alternatif yang bagus.
Ketahui wadah Anda
std::unordered_mapadalah temanmu dalam masalah ini. Kapan pun Anda belum pernah melihat angka, cukup gunakan fungsi operator[]atau insertuntuk menambahkan angka dan indeksnya. Saat menggunakan find, itu akan mengembalikan iterator, yang merupakan key-valuepasangan.
misalnya: auto location = m.find(numToFind);
location->firstadalah kunci Anda, dan location->secondnilai Anda
Saat Anda kembali, jangan gunakan push_back
Anda hanya dapat mengembalikan daftar initializer seperti: {i,j}.