สารบัญ

1. คุณสามารถเดาชื่ออาหารได้หรือไม่?
2. 1 ผลรวม
3. 2ผลรวม
4. 3 ผลรวม
5. 4 ผลรวม
6. KSum
7. สรุป
8. โพสต์ถัดไป

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

หลังจากทานอาหารเย็นเสร็จ คนรักในวัยเด็กของคุณแนะนำให้เล่นเกม“เดาอาหาร” แต่คราวนี้ แทนที่จะเดาชื่ออาหาร คุณต้องบอกชื่อส่วนผสมของอาหารลึกลับนี้อย่างน้อยหนึ่งอย่าง คุณต้องการทำให้เธอประทับใจ ดังนั้นคุณจึงนึกถึงคำถามนี้:

คุณจะเดาชื่อของส่วนผสมเหล่านี้ได้อย่างรวดเร็วก่อนที่จะเทน้ำเย็นใส่ถังใส่หัวคุณได้อย่างไร?

มาดูกันว่าโพสต์นี้สามารถช่วยเราพัฒนาวิธีการที่มีประสิทธิภาพในการค้นหาส่วนผสมเหล่านั้นได้อย่างรวดเร็วได้อย่างไร

เราจะเริ่มซีรีส์นี้ด้วยKSum Family Problems หนึ่งในคำถามที่ถูกถามบ่อยที่สุดในหมู่ผู้สัมภาษณ์ เพราะมันมีรูปแบบการแก้ปัญหามากมายที่คุณเห็นได้จากปัญหาอัลกอริทึมอื่นๆ เกือบทั้งหมด นอกจากนี้ยังช่วยให้ผู้สัมภาษณ์สามารถขยายคำถามจากปัญหา KSum ประเภทหนึ่งไปยังปัญหา KSum เวอร์ชันอื่นได้อย่างง่ายดาย

ในปัญหาประเภทนี้ เราคือ:

จากรายการจำนวนเต็มเราต้องการค้นหากลุ่มของตัวเลข K ทั้งหมด ที่รวมกันเป็นเป้าหมายที่ กำหนด ด้วยวิธีนี้ กลุ่มเหล่านี้ทั้งหมดควรไม่ซ้ำกัน

ในทางคณิตศาสตร์ สามารถจัดรูปแบบเป็น:

เอาล่ะมาเริ่มกันเลย!

2. 1 ผลรวม

1.1 คำอธิบายปัญหา

นี่คือ KSum เวอร์ชันแรกของเรา ซึ่งถือว่าเป็นปัญหาในการค้นหาแต่ที่นี่ เรากำหนดใหม่ให้เป็นเวอร์ชันที่ง่ายที่สุดของ KSum (1 มิติ)

ในปัญหานี้:

เราได้รับรายการหมายเลขเฉพาะและต้องการหาดัชนีของตัวเลขที่ตรงกับเป้าหมาย ที่กำหนด

A + 0 = เป้าหมาย

1.2 ตัวอย่าง

อินพุต: nums = [6,2,5,4,11], เป้าหมาย = 4

ผลลัพธ์:ดัชนีคือ 3

นี่คือตัวอย่างอินพุตสำหรับอัลกอริทึมของเราและสิ่งที่ควรส่งคืน หากอัลกอริทึมได้รับรายการnums = [6,2,5,4,11]และเป้าหมาย = 4 ดังนั้น หากพบเป้าหมายนี้ในรายการ อัลกอริทึมควรส่งคืนดัชนีซึ่งอยู่ที่นี่3

1.3 โซลูชั่นเดรัจฉานฟอร์ซ

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

ความซับซ้อนของเวลาสำหรับโซลูชันนี้คือ:

ในกรณีที่เลวร้ายที่สุด เป้าหมายจะอยู่ที่ส่วนท้ายของรายการหรือไม่มีอยู่ และเราจะทำซ้ำกับหมายเลขรายการทั้งหมด

และความซับซ้อนของพื้นที่สำหรับโซลูชันนี้จะเป็น:

ไม่ใช้พื้นที่พิเศษ!

1.4 โซลูชันที่เพิ่มประสิทธิภาพ

สมมติว่ารายการตัวเลขของเราถูกจัดเรียง . จากนั้น ความซับซ้อนของเวลาอาจลดลงเหลือ O( log n)โดยใช้อัลกอริทึม Binary Search แต่เพื่อประโยชน์ในการพึ่งพากันของแนวคิดของปัญหาในโพสต์นี้ เราจะหารือเกี่ยวกับวิธีแก้ปัญหาอื่น

โซลูชันนี้เร็วกว่าโซลูชันไร้เดียงสาในแง่ของความซับซ้อนของเวลา อัลกอริทึมการค้นหาแบบไบนารียังดีกว่า ตอนนี้คุณเดาวิธีแก้ปัญหานี้แล้วหรือยัง! ใช่แล้ว; ไชโย! เป็นแนวทางสองพอยน์เตอร์

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

• เริ่มต้นตัวชี้สองตัว: ตัวชี้ซ้ายที่มีค่าเท่ากับซ้าย = 0และตัวชี้ขวาที่มีค่าเท่ากับขวา= n-1โดยที่n = ขนาดอาร์เรย์
• จากนั้นเราตรวจสอบว่าnums[left] == ​​targetหรือไม่ จากนั้นเพิ่มตัวชี้ด้านซ้าย 1
• นอกจากนี้ เราตรวจสอบว่าnums[right] == ​​targetแล้วลดตัวชี้ขวาลง 1

นี่คือรหัสจริง:

อีกครั้ง ความซับซ้อนของเวลายังคงเป็น:

ในสถานการณ์ที่เลวร้ายที่สุด แต่เมื่อเทียบกับวิธีการไร้เดียงสานั้นเร็วกว่ามากเนื่องจากใช้พอยน์เตอร์สองตัวในการตรวจสอบพร้อมกัน

ความซับซ้อนของพื้นที่คือ

ไม่มีพื้นที่พิเศษ

1.5 รูปแบบ

ในปัญหานี้ เรามีรูปแบบดังต่อไปนี้:

• ตัวชี้สองตัว : เมื่อคุณมีการดำเนินการค้นหาในรายการ( เรียงลำดับหรือไม่ ) หรือคอลเลกชัน ให้นึกถึงการใช้ตัวชี้สองตัวเพื่อสำรวจคอลเลกชันนั้นอย่างรวดเร็ว

2.1 คำอธิบายปัญหา

นี่คือสมาชิกคนที่สองของครอบครัว KSum ในปัญหานี้:

เราได้รับรายการจำนวนเต็มเฉพาะและต้องการหาดัชนีของตัวเลขสองตัวที่รวมกันเป็นเป้าหมายที่กำหนด เนื่องจากมีเพียงคู่เดียวที่เป็นเป้าหมาย

A + B = เป้าหมาย

2.2 ตัวอย่าง

อินพุต: nums = [6,2,4,3,11], เป้าหมาย = 15

เอาต์พุต: [2,4] — > nums[2] + nums[4] = 15

นี่คือตัวอย่างอินพุตและเอาต์พุตของอัลกอริทึมของเรา หากอัลกอริทึมได้รับรายการnums = [6,2,5,4,11]และเป้าหมาย = 15หากพบเป้าหมายนี้ในรายการ อัลกอริทึมควรส่งคืนดัชนีของตัวเลขสองตัวที่ผลรวมของพวกมันเท่ากับ เป้าหมายซึ่งอยู่ที่นี่2และ4

2.3 โซลูชั่นเดรัจฉานฟอร์ซ

วิธีที่ใช้งานง่ายในการแก้ปัญหานี้คือการสร้างตัวแปรลูปสองตัว(i, j ) จากนั้น เราจะมองหาผลรวมของตัวเลขสองตัวที่รวมกันเป็นค่าเป้าหมาย มาดูกันว่าเราเขียนโค้ดนี้อย่างไร:

ความซับซ้อนของเวลาจะเป็น:

เนื่องจากเราใช้ลูปที่ซ้อนกัน 2 ลูป ซึ่งจะส่งผลให้เกิดความซับซ้อนของเวลาในสถานการณ์ที่เลวร้ายที่สุด

ความซับซ้อนของอวกาศคือ:

โอกาสในการเพิ่มประสิทธิภาพ:แม้ว่าอัลกอริทึมนี้จะมีประสิทธิภาพในแง่ของความซับซ้อนของพื้นที่O(1)แต่ก็ไม่สามารถใช้ได้จริงในแง่ของความซับซ้อนของเวลา เราสามารถลดความซับซ้อนของเวลาจากO(n²) ⇾ O(n)ได้ไหม

2.4 โซลูชันที่เพิ่มประสิทธิภาพ

โครงสร้างข้อมูลที่มี ประโยชน์ที่สุดอย่างหนึ่งที่โปรแกรมเมอร์ชอบใช้คือHashmap มี ความซับซ้อนด้านเวลา O(1)สำหรับการดำเนินการค้นหาองค์ประกอบเกือบทั้งหมดภายในนั้น เราสามารถแก้ไขความไร้ประสิทธิภาพของโซลูชันเดรัจฉานได้โดยอาศัยความซับซ้อนของพื้นที่

ดังนั้นเราจึงสามารถเก็บตัวเลขทั้งหมดไว้ในHashmap จากนั้นเราสามารถวนซ้ำรายการ และทุกเมื่อ เราจะสอบถาม Hashmap ของเราโดยใช้คีย์ที่มีค่าเท่ากับเป้าหมาย — nums[i]โดยที่iคือตัวแปรวนซ้ำ และnumsคือรายการของตัวเลข มาดูกันว่าเราเขียนโค้ดนี้อย่างไร:

จากนั้นความซับซ้อนของเวลาจะเป็น:

แต่ความซับซ้อนของพื้นที่จะเป็น:

ใช่ ฉันรู้ ฉันรู้! เป็นการแลกเปลี่ยนระหว่างการเพิ่มประสิทธิภาพความซับซ้อนของเวลากับความซับซ้อนของพื้นที่

2.5 รูปแบบ

• Hashmap:ตามหลักทั่วไป ให้พิจารณาใช้Hashmap เสมอ หากคุณต้องการจัดเก็บค่ากลางหรือเพิ่มประสิทธิภาพเวลาในการค้นหาของคอลเลกชัน

3.1 คำอธิบายปัญหา

นี่ เป็นอีกเวอร์ชันหนึ่งจากตระกูลปัญหา KSum ในปัญหานี้:

เราได้รับรายการของจำนวนเต็มที่ไม่ซ้ำกัน และเราต้องการหาตัวเลขสามตัวที่รวมกันแล้วได้ศูนย์ ด้วยวิธีนี้แฝดสามควรจะมีเอกลักษณ์เฉพาะตัว

เอ + บี + ค = 0

3.2 ตัวอย่าง

อินพุต: nums = [-1,0,1,2,-1,-4], เป้าหมาย = 0

เอาต์พุต: [ [-1,-1,2], [-1,0,1] ] , ไม่ใช่ [ [-1,-1,2], [-1,0,1], [1,0,- 1],]

นี่คือตัวอย่างอินพุตและเอาต์พุตของอัลกอริทึมของเรา หากอัลกอริทึมได้รับรายการnums = [-1,0,1,2,-1,-4]และเป้าหมาย = 0หากพบเป้าหมายนี้ในรายการ อัลกอริทึมควรส่งคืนดัชนีของตัวเลขทั้งสาม ซึ่งผลรวมเท่ากับศูนย์ซึ่งอยู่ที่นี่[ [-1,-1,2], [-1,0,1] ]

3.3 โซลูชั่นเดรัจฉานฟอร์ซ

อีกครั้ง วิธีที่ใช้งานง่ายในการแก้ปัญหาคือการสร้างตัวแปรสามลูป(i, j, k ) จากนั้น เรามองหาผลรวมของตัวเลขสามตัวที่รวมกันแล้วได้ศูนย์ ในโค้ดด้านล่าง ให้สังเกตว่าการจัดเรียงที่เราทำในตอนแรกอนุญาตให้Python ตั้งค่า "ผลลัพธ์"เพื่อจดจำชุดค่าผสมที่ซ้ำกันได้ อย่างไร

ความซับซ้อนของเวลาสำหรับโซลูชันนี้คือ:

เพราะใช้สามลูปที่ซ้อนกัน!

ความซับซ้อนของอวกาศคือ:

เพราะเราใช้ชุด"ผลลัพธ์" ของ python เพื่อจัดเก็บชุดค่าผสม

โอกาสในการเพิ่มประสิทธิภาพ:เราสามารถลดความซับซ้อนของเวลาจาก O(n³) ⇾ O(n) ได้หรือไม่

3.4 โซลูชันที่เพิ่มประสิทธิภาพ

อีกครั้ง คำตอบคือใช่! และนั่นคือโดยใช้วิธี"สองพอยน์เตอร์" แนวคิดมีดังนี้:

1. จัดเรียงอาร์เรย์ของจำนวนเต็มตามลำดับที่เพิ่มขึ้น
2. สร้างชุดสำหรับการรวมกันของสามแฝดที่เรียกว่า"ผลลัพธ์"
3. ในขณะที่วนซ้ำอาร์เรย์โดยใช้ตัวแปร ( i)
4. เริ่มต้นตัวชี้สองตัว ตัวชี้ซ้ายที่มีค่าเท่ากับi+1และตัวชี้ขวาที่มีค่าเท่ากับn-1โดยที่ n = ขนาดอาร์เรย์
5. สร้างลูปที่ซ้อนกันและสำรวจอาร์เรย์โดยใช้พอยน์เตอร์สองตัว เนื่องจากเรากำลังมองหา nums[left] + nums[right] + nums[i]= 0เราจึงกำหนดเป้าหมาย = -nums[i]
6. ถ้า nums[left] + nums[right] = targetเราจะเพิ่มสิ่งนี้ให้กับชุดผลลัพธ์
7. ถ้า nums[left] + nums[right] < targetหมายความว่าเราต้องเพิ่มตัวชี้ซ้ายเพื่อเพิ่มค่าของผลรวมนี้
8. สุดท้ายหาก nums[left] + nums[right] > targetหมายความว่าเราต้องลดตัวชี้ด้านขวาเพื่อลดค่าของการรวมและดันให้เป็นศูนย์
9. ในท้ายที่สุด เราจะส่งคืน " ผลลัพธ์"

ความซับซ้อนของเวลาจะเป็น:

ซึ่งเป็นความซับซ้อนของเวลาที่ดีกว่าเล็กน้อยเมื่อเทียบกับ O( n³ ) เราใช้สองการดำเนินการหลัก การเรียงลำดับO(n.logn)และการค้นหาO(n²) (ลูปที่ซ้อนกันสองลูป) อย่างไรก็ตาม ความซับซ้อนของเวลายังคงเป็นO(n²)เพราะO(n.logn) + O(n²) = O(n²)

ความซับซ้อนของอวกาศจะเป็น:

แต่ก็ยังคล้ายกับวิธีแก้ปัญหาแบบเดรัจฉาน หนีไม่พ้น!

3.5 รูปแบบ

• การเรียงลำดับ:การเรียงลำดับเป็นหนึ่งในขั้นตอนการประมวลผลล่วงหน้าที่สำคัญที่สุดเมื่อแก้ปัญหาอัลกอริทึม โดยเฉพาะปัญหาอาร์เรย์ (รายการ) มันทำให้ปัญหาถูกละเมิดได้ง่ายขึ้นมาก ดังนั้นลองพิจารณาการเรียงลำดับอาร์เรย์ของคุณสักครู่เมื่อคุณแก้ปัญหาอาร์เรย์
• การใช้โครงสร้างข้อมูล Python “Set”: เอาชนะค่าที่ซ้ำๆ โดยใช้ โครงสร้างข้อมูลPython “set” มีคุณสมบัติในการกำจัดค่าที่ซ้ำกันโดยอัตโนมัติ ที่นี่ ฉันใช้มันเพื่อจัดเก็บชุดค่าผสมในขณะที่ลบรายการที่ซ้ำกัน
• ตัวชี้สองตัว:เราใช้ตัวชี้สองตัวเพื่อสำรวจรายการเร็วขึ้น สังเกตว่าการใช้แนวทางนี้ง่ายขึ้นอย่างไรหลังจากเรียงลำดับค่ารายการ

4.1 คำอธิบายปัญหา

นี่จะเป็น ปัญหาสุดท้ายของเราจากตระกูล KSumก่อนที่จะพูดถึงKSum รุ่นทั่วไป เมื่อคุณสังเกตเห็น รูปแบบของการแก้ปัญหาเหล่านี้จะชัดเจนขึ้น และฉันพนันได้เลยว่าคุณก็เริ่มรู้สึกได้เช่นกัน ดังนั้น,

จากรายการของ จำนวน เต็มที่ไม่ซ้ำกันและเป้าหมาย เราต้องการค้นหาชุดของ ตัวเลข 4 ตัวใดๆ จาก รายการนี้ที่รวมเข้ากับเป้าหมายนั้น โดยที่ชุดเหล่านั้นล้วนไม่ซ้ำกัน
A + B + C + D = เป้าหมาย

4.2 ตัวอย่าง

อินพุต: nums = [3,7,2,4,5,4,6,1,8], เป้าหมาย = 12
เอาต์พุต: [[1, 2, 3, 6], [1, 2, 4, 5], [1, 3, 4, 4]]

นี่คือตัวอย่างอินพุตและเอาต์พุตของอัลกอริทึมของเรา หากอัลกอริทึมได้รับรายการnums = [3,7,2,4,5,4,6,1,8]และเป้าหมาย = 12ดังนั้นหากพบเป้าหมายนี้ในรายการ อัลกอริทึมควรส่งคืนดัชนีของ ตัวเลขสามตัวที่ผลรวมเท่ากับศูนย์ซึ่งอยู่ที่นี่[[1, 2, 3, 6], [1, 2, 4, 5], [1, 3, 4, 4]]

4.3 วิธีแก้ปัญหาแบบเดรัจฉาน

เช่นเดียวกับ 3Sum วิธีแก้ไขปัญหานี้คือการสร้างตัวแปรสี่ ลูป(i, j, k, l) จากนั้น เราจะมองหาผลรวมของตัวเลขสี่ตัวที่รวมกันเป็นค่าเป้าหมายนั้น คุณไม่จำเป็นต้องเขียนโค้ดโซลูชันนี้! ตอนนี้กลายเป็นเค้กชิ้นหนึ่งไปแล้ว

4.4 โซลูชันที่เพิ่มประสิทธิภาพ

เวอร์ชันที่ปรับให้เหมาะสมของ 4Sum นั้นคล้ายกับโซลูชันที่ปรับให้เหมาะสมของ 3Sum มาก โปรดสังเกตในโค้ดด้านล่าง เราเพิ่งเพิ่มอีกหนึ่งลูป ( ลูปที่สอง ) ในขณะที่ยังคงลูปสองพอยน์เตอร์( ลูปที่สาม) ให้เราดูรหัสด้านล่าง:

ความซับซ้อนของเวลาคือ:

เพราะเราใช้สามลูป

และความซับซ้อนของอวกาศจะเป็น:

เนื่องจากเราต้องการเก็บผลลัพธ์

6. กศน

ในที่สุดเราก็ได้พบกับสัตว์ร้าย! KSum _ ปัญหา 2Sum, 3Sum และ 4Sum ทำให้เรามีรูปแบบในการแก้ปัญหา KSum (เช่น 5Sum, 6Sum)

5.1 คำอธิบายปัญหา

ในการอนุมาน โซลูชัน KSumจากโซลูชันก่อนหน้านี้ เราต้องเข้าใจสิ่งที่สำคัญมากก่อน ปัญหา KSum สามารถแก้ไขได้ด้วยแนวคิดง่ายๆ นี้:

ลดปัญหา KSum เป็น 2Sum แล้วแก้ปัญหา

ใช่ เราต้องลด KSum เป็น 2Sum แล้วแก้ปัญหา! แต่ก่อนอื่น เพื่อให้เข้าใจรูปแบบการแก้ปัญหานี้ เราต้องทบทวนสมการง่ายๆ เหล่านี้อีกครั้ง:

ปัญหา 2Sumสามารถจัดรูปแบบเป็น:

ในขณะที่3Sumถูกทำให้เป็นทางการ เป็น:

และ4Sumมีรูปแบบ เป็น:

จากนั้นในการแก้ผลรวม 4เราสามารถจัดเรียงสมการเหล่านี้ใหม่ได้ดังนี้:

เดี๋ยวก่อน เดี๋ยวก่อน วาลีด ฉันกำลังจะหลงทาง คุณช่วยอธิบายเพิ่มเติมได้ไหม อย่างแน่นอน! ขอให้เราใช้ 4Sum เป็นตัวอย่าง เราจะเห็นว่าเพื่อให้สามารถคำนวณได้ ให้เราเรียกมันว่าเป้าหมายระดับล่าง (เช่น “ t₁”)เราต้องการเป้าหมายระดับบน “ t₂”และ“ตัวเลข” “ตัวเลข” ในที่นี้หมายถึงเทอม 4ₜₕในสมการ

จากนั้น เพื่อแก้ปัญหา 4Sum เราจำเป็นต้องคำนวณเป้าหมายเหล่านี้โดยเริ่มย้อนกลับโดยมีเป้าหมายระดับบนสุด (เช่น “ t₃”)ซึ่งจะได้รับเสมอ

ในที่สุด เราสามารถหาองค์ประกอบสองตัวสุดท้ายในสมการ( a, b)โดยใช้ วิธี ตัวชี้สองตัวที่เราเห็นก่อนหน้านี้ใน2Sum ข่าวดีก็คือ เราสามารถใช้แนวคิดที่ถูกต้องในการแก้ปัญหาKSum ได้

5.2 วิธีแก้ไข

นี่คือบทสรุปของอัลกอริทึมด้านบน:

เริ่มต้นด้วยเป้าหมายองศาบนสุด (เช่นองศา = 3, t = “ t₃” ):

1. คำนวณเป้าหมายระดับบนซ้ำ(t₂, t₁)
2. เมื่อองศา = 2ให้เรียกใช้ฟังก์ชัน 2Sumเพื่อค้นหาองค์ประกอบสุดท้ายที่ขาดหายไป(a, b)


เอาล่ะ เอาล่ะ นี่คือคำอธิบายภาพว่าอัลกอริทึมด้านบนทำงานอย่างไร:



ตอนนี้นี่คือรหัส เพื่อความเข้าใจที่ดีขึ้น ให้เชื่อมต่อทุกบรรทัดในโค้ดด้วยขั้นตอนที่สอดคล้องกันในภาพประกอบด้านบน

หากเราไม่ดำเนินการเรียงลำดับความซับซ้อนของเวลาจะเป็นดังนี้:

โดยที่ k = องศาหรือจำนวนของส่วนประกอบที่ขาดหายไป และ n = ขนาดอาร์เรย์

และความซับซ้อนของอวกาศคือ:

ละเว้นหน่วยความจำที่ใช้โดยตัวแปร " เส้นทาง"

5.3 รูปแบบและเทคนิค

• Depth First Search (DFS):เราใช้อัลกอริทึมการค้นหาแบบ Depth-First เพื่อสำรวจรายการตัวเลขโดยอัปเดตระดับ (k)และค่าเป้าหมาย
• ตัวชี้สองตัว:เราใช้เวอร์ชันที่ปรับให้เหมาะสม(พร้อมตัวชี้สองตัว)ของ 2Sum เพื่อค้นหาองค์ประกอบสุดท้ายที่ขาดหายไป(a, b)

ในโพสต์นี้เราได้กล่าวถึงปัญหาครอบครัว KSum ปัญหาประเภทนี้ทำให้เรารู้จักรูปแบบอัลกอริทึมที่สำคัญบางรูปแบบที่สามารถสรุปได้ดังนี้

รูปแบบปัญหา:

1. ปัญหาที่ทำให้คุณต้องมองหาชุดของตัวเลข (subarray) ในอาร์เรย์เพื่อให้ตรงกับค่าการรวมที่กำหนด (ผลรวม สูงสุด นาที … ฯลฯ) → พยายามใช้ตัวชี้สองตัว [1] [2]
2. ปัญหาที่ต้องค้นหาชุดของชุดค่าผสมหรือชุดย่อยของโซลูชัน → ลองใช้อัลกอริทึมการค้นหาแบบลึกก่อน (DFS) [3] [4]
1. สำหรับการค้นหารายการอย่างรวดเร็ว→ พยายามใช้โครงสร้างข้อมูลแฮชแมป
2. หากต้องการลบรายการที่ซ้ำกันในรายการหรือคอลเลกชัน→ ลองใช้โครงสร้างข้อมูลชุดไพธอน


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

คุณควรทำความฝันให้สำเร็จตามลำดับใด

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

ขอบคุณสำหรับการอ่านของคุณ!

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

หากคุณมีคำถามหรือความคิดเห็นอื่นๆ โปรดอย่าลังเลที่จะแบ่งปันกับฉันผ่านMedium | ลิงค์ดิน | ทวิตเตอร์ | หรืออีเมล _ แล้วพบกันใหม่!

ทรัพยากร

[1] T. Cormen et al.,
Introduction to Algorithms , พิมพ์ครั้งที่ 4 (2022), The MIT Press

[2] Amit Singh Rathore , Two Pointers Approach — Python Code (2021), Medium.com

[3] ทีมคำตอบเพื่อการศึกษา การค้นหาเชิงลึกก่อนคืออะไร (2023), Educative.io.

[4] Educative Answers Team, วิธีการใช้การค้นหาเชิงลึกก่อนใน Python (2023), Educative.io

เพิ่มระดับการเข้ารหัส

ขอบคุณที่เป็นส่วนหนึ่งของชุมชนของเรา! ก่อนที่คุณจะไป:

• ปรบมือให้กับเรื่องราวและติดตามผู้เขียน
• ดูเนื้อหาเพิ่มเติมในสิ่งพิมพ์ Level Up Coding
• หลักสูตรสัมภาษณ์การเข้ารหัสฟรี ⇒ ดูหลักสูตร
• ติดตามเรา: Twitter | LinkedIn | จดหมายข่าว