Leetcode สองผลรวม

Question

ฉันกำลังเรียนรู้ c ++ ที่มาจากพื้นหลัง python ดังนั้นฉันจะรวมวิธีแก้ปัญหาใน python และใน c ++ สำหรับคำสั่งปัญหาต่อไปนี้:

เมื่อกำหนดอาร์เรย์ของจำนวนเต็มและจำนวนเต็มเป้าหมายให้ส่งกลับดัชนีของตัวเลขสองจำนวนดังกล่าวเพื่อรวมเข้ากับเป้าหมาย คุณอาจสันนิษฐานได้ว่าอินพุตแต่ละรายการจะมีโซลูชันเดียวเท่านั้นและคุณไม่สามารถใช้องค์ประกอบเดียวกันซ้ำได้ คุณสามารถส่งคืนคำตอบในลำดับใดก็ได้

ตัวอย่างที่ 1:

อินพุต: nums = [2,7,11,15] เป้าหมาย = 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 ms เร็วกว่า 36.98% ของการส่ง Python ออนไลน์สำหรับ Two Sum การใช้หน่วยความจำ: 14.4 MB น้อยกว่า 49.82% ของการส่ง Python ออนไลน์สำหรับ 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");
}

สถิติ Leetcode:

รันไทม์: 384 ms เร็วกว่า 34.03% ของการส่ง C ++ ออนไลน์สำหรับ Two Sum การใช้หน่วยความจำ 9.3 MB น้อยกว่า 12.99% ของการส่ง C ++ ออนไลน์สำหรับ Two Sum

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(ที่มีการดำเนินการ) เป็นหลายไฟล์คุณจะต้องทำลายกฎข้อหนึ่ง-Definition ไฟล์ต้นฉบับของคุณจะมีคำจำกัดความของฟังก์ชันเดียวกันหลายคำและตัวเชื่อมโยงจะคายข้อผิดพลาดออกมา วิธีหนึ่งในการหลีกเลี่ยงคือการทำเครื่องหมายฟังก์ชันinlineแต่คุณมักจะต้องการทำแบบเดิม

ไม่มีusing namespaceในไฟล์ส่วนหัว

อย่าทำusing namespaceหรือตัวแปรใด ๆ ในไฟล์ส่วนหัว เนื่องจากไฟล์ส่วนหัวถูกคัดลอกไปวางในไฟล์ต้นฉบับหลายไฟล์จึงมีโอกาสที่จะทำให้เกิดข้อผิดพลาดที่น่ารำคาญ ดูที่นี่

ใช้การอ้างอิง const

เนื่องจากtwo_sum_solutionไม่ได้แก้ไขnumsเวกเตอร์ให้ส่งต่อโดยการอ้างอิง const

size_t เทียบกับ int สำหรับดัชนีอาร์เรย์

พิจารณาใช้ size_t แทน int สำหรับดัชนีอาร์เรย์

ใช้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. ค้นหาและส่งคืนดัชนีจากแผนที่ / 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

Answer 4

สิ่งนี้น่าสนใจสำหรับฉันเพราะฉันมาจากพื้นหลัง C และเริ่มใช้ Python ในช่วงสองสามปีที่ผ่านมาในการทำงานดังนั้นฉันจึงมีเส้นทางย้อนกลับเหมือนคุณ เมื่อฉันเริ่ม 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 ซึ่งเป็นไลบรารีมาตรฐานที่มีประสิทธิภาพในสายงานของฉัน (วิทยาศาสตร์ข้อมูล) แต่นั่นไม่เป็นความจริงทุกที่

สิ่งหนึ่งที่แตกต่างจากรหัสของคุณ: ไม่มีที่ว่างสำหรับข้อผิดพลาดแบบ off-by-one-error จากประสบการณ์ของฉันรหัสเช่นนี้

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

เป็นเรื่องง่ายสำหรับฉันที่จะเขียนอ่านยากและบำรุงรักษาครอบคลุมกลเม็ดทั้งหมดจากง่ายไปหาไม่ได้ กล่าวอีกนัยหนึ่งการจัดการดัชนีด้วยตนเองใน Python ทำให้ฉันมีเชือกเพียงพอที่จะแขวนคอตัวเองได้และฟังก์ชันห้องสมุดมาตรฐานก็เป็นทางเลือกที่ดี

Answer 5

รู้จักภาชนะของคุณ

std::unordered_mapเป็นเพื่อนของคุณในปัญหานี้ เมื่อใดก็ตามที่คุณไม่เคยเห็นตัวเลขมาก่อนเพียงแค่ใช้ฟังก์ชันoperator[]หรือinsertเพื่อเพิ่มตัวเลขและดัชนี เมื่อใช้findมันจะส่งคืนตัววนซ้ำซึ่งเป็นkey-valueคู่

เช่น: auto location = m.find(numToFind);

location->firstคือกุญแจสำคัญและ location->secondเป็นคุณค่าของคุณ

เมื่อคุณกลับมาอย่าใช้ push_back

คุณก็สามารถกลับรายการ initializer {i,j}เช่น: