مؤشران في مصفوفة مرتبة

تفحص تقنية المؤشرين مصفوفةً باستخدام فهرسين بدلًا من الحلقات المتداخلة، فتحوّل كثيرًا من الأفكار ذات التعقيد O(n^2) إلى مرور واحد واضح بتعقيد O(n). 🎯

تحتاج الطريقة التقليدية إلى مصفوفة مرتبة. فالترتيب يساعدك على الاستدلال: التحرك يمينًا يزيد القيمة، والتحرك يسارًا يقللها، ولذلك تمثل كل خطوة قرارًا حقيقيًا.

ابدأ بمؤشر عند الطرف left ومؤشر آخر عند الطرف right. يواجه المؤشران أحدهما الآخر، وسيقلّصان المسافة بينهما تدريجيًا.

في كل خطوة، حرّك مؤشرًا واحدًا فقط إلى الداخل. ويخبرك ترتيب المصفوفة بأي جانب ينبغي دفعه قليلًا للاقتراب من هدفك.

واصل التكرار ما دام left < right. وعندما يلتقي المؤشران أو يتجاوز أحدهما الآخر، تكون قد فحصت كل زوج مفيد ويمكنك التوقف.

اعتبر a[left] + a[right] مرشحك الحالي. وتخبرك مقارنته بالهدف بما إذا كنت تحتاج إلى قيمة أكبر أم أصغر بعد ذلك.

إذا كان المجموع أقل من الهدف، فأنت تحتاج إلى المزيد. حرّك مؤشر left إلى اليمين باتجاه القيم الأكبر، لأن المصفوفة مرتبة تصاعديًا.

إذا كان المجموع أكبر من الهدف، فأنت تحتاج إلى الأقل. حرّك مؤشر right إلى اليسار باتجاه القيم الأصغر لخفض المجموع.

تؤدي كل حركة إلى استبعاد مجموعة كاملة من الأزواج التي لا تحتاج إلى اختبارها. ولهذا يكون الفحص خطيًا بدلًا من أن يكون تربيعيًا.

أنت تستبعد فقط الأزواج التي لا يمكن أن تطابق الهدف، ولذلك لا تتجاوز الإجابة الصحيحة أبدًا. وهذه السلامة هي ما يجعل المؤشرين موثوقين في المسابقات.

تدعم الفكرة نفسها أنواعًا مختلفة من المسائل: العكس في المكان، والتقسيم، والدمج. وعندما تتقن مؤشري الالتقاء، ستبدو هذه المسائل مألوفة جميعًا.

أنت تفحص مصفوفة مرتبة من الطرفين بحثًا عن مجموع مستهدف.

يمسح المؤشران مصفوفة مرتبة من طرفيها، ويحرّك أحدهما إلى الداخل في كل خطوة ما دام left < right. إنها طريقة خطية وصحيحة، وتشكل أساسًا لكثير من الحيل. 🚀