ตัวชี้สองตัวบนอาร์เรย์ที่เรียงแล้ว

เทคนิค ตัวชี้สองตัว จะสแกนอาร์เรย์ด้วยดัชนีสองตัวแทนการใช้ลูปซ้อน ทำให้แนวคิด O(n^2) หลายแบบกลายเป็นการประมวลผล O(n) เพียงรอบเดียวที่เป็นระเบียบ 🎯

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

เริ่มต้นตัวชี้หนึ่งตัวที่ ปลายด้านซ้าย และอีกตัวที่ปลายด้านขวา ตัวชี้ทั้งสองจะหันเข้าหากันและค่อย ๆ ลดระยะห่างระหว่างกัน

ในแต่ละขั้นตอน ให้ เลื่อนตัวชี้เข้าด้านในเพียงหนึ่งตัว ลำดับของอาร์เรย์จะบอกว่าควรขยับด้านใดเพื่อเข้าใกล้เป้าหมายมากขึ้น

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

พิจารณา a[left] + a[right] เป็นค่าผู้สมัครปัจจุบัน การเปรียบเทียบค่านี้กับเป้าหมายจะบอกว่าขั้นถัดไปต้องการค่าที่มากขึ้นหรือน้อยลง

หากผลรวมต่ำกว่าเป้าหมาย คุณต้องการค่าที่ มากขึ้น ให้เลื่อนตัวชี้ด้านซ้ายไปทางขวาเพื่อไปยังค่าที่มากขึ้น เนื่องจากอาร์เรย์เรียงจากน้อยไปมาก

หากผลรวมสูงกว่าเป้าหมาย คุณต้องการค่าที่ น้อยลง ให้เลื่อนตัวชี้ด้านขวาไปทางซ้ายเพื่อไปยังค่าที่น้อยลงและลดผลรวม

การเลื่อนแต่ละครั้งจะ ตัดทิ้งคู่ค่าจำนวนมากที่ไม่จำเป็นต้องตรวจสอบอีก นี่คือเหตุผลที่การสแกนใช้เวลาเชิงเส้นแทนเวลาเชิงกำลังสอง

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

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

คุณกำลังสแกนอาร์เรย์ที่เรียงลำดับแล้วจากปลายทั้งสองด้านเพื่อหาผลรวมเป้าหมาย

ตัวชี้สองตัวจะกวาดผ่านอาร์เรย์ที่ เรียงลำดับแล้วจากปลายทั้งสองด้าน โดยเลื่อนเข้าด้านในทีละตัวตราบใดที่ left < right ใช้เวลาเชิงเส้น ถูกต้อง และเป็นพื้นฐานของเทคนิคอีกมากมาย 🚀