3Sum

رتّب القائمة أولًا. بعد ذلك، تعطي أي ثلاثة مواضع i < j < k قيمًا مرتبة بالفعل، nums[i] ≤ nums[j] ≤ nums[k]، لذا تكون الثلاثية مكتوبة بالترتيب الصحيح بمجرد العثور عليها. تمرّ ثلاث حلقات متداخلة على كل اختيار ممكن للمواضع، لذا لا يمكن أن تفوتنا أي ثلاثية.

بعد ذلك تأتي القيم المكررة. بعد الترتيب، يصبح المثال الأول [-2, -1, 0, 1, 1, 2]، ويمكن أن تأخذ [-1, 0, 1] القيمة 1 من الفهرس 3 أو الفهرس 4. لذلك تتخطى كل حلقة موضعًا تكون قيمته مساوية للقيمة التي جرّبتها الحلقة نفسها قبله. وهكذا تجرّب كل حلقة كل قيمة مميزة مرة واحدة، وتظهر كل ثلاثية مميزة مرة واحدة، وبترتيب تصاعدي من البداية. لا تقارن عملية التخطي إلا بالموضع السابق داخل الحلقة نفسها، لذا تظل [-2, 1, 1] تستخدم الواحدين كليهما.

المشكلة هي التكلفة. هناك نحو n³/6 ثلاثيات: وهذا يعني 4.5 × 10^9 مجموعًا لـ 3000 عدد، وهو ما يتجاوز بكثير أي حد زمني.

بعد تثبيت القيمة الأولى nums[i]، تحتاج إلى قيمتين لاحقتين يكون مجموعهما -nums[i]. هذه هي مسألة Two Sum. حرّك j إلى يمين i واحتفظ بمجموعة من القيم التي مررت بها. عند كل j، تكون القيمة الناقصة هي need = -nums[i] - nums[j]. إذا كانت need في المجموعة، فإن [nums[i], need, nums[j]] يكون مجموعها 0. يستغرق البحث في المجموعة O(1) في المتوسط، لذا تكون كلفة قيمة واحدة لـ i هي O(n)، وكلفة البحث بالكامل O(n²).

ما زال الترتيب يتولى تنظيم الأمور. تخطَّ أي i تكون قيمته مساوية للقيمة التي قبله. بعد العثور على تطابق، حرّك j متجاوزًا كل نسخة من nums[j]: فمع تثبيت القيمتين الأولى والثالثة، تكون القيمة الوسطى ثابتة أيضًا، لذا لا يمكن لنسخة أخرى إلا أن تكرر الثلاثية نفسها. وبما أن need تأتي من موضع أسبق في القائمة المرتبة، فإن need ≤ nums[j] وتكون الثلاثية مرتبة. يمكنك أيضًا التوقف بمجرد أن يصبح nums[i] > 0: فالقيمتان التاليتان لا تقلان عنه، لذا لا يمكن أن يصل المجموع إلى 0.

ملاحظة: كلما تحرك j إلى اليمين، تزداد nums[j] وتتناقص need، لذا تخرج الثلاثيات لقيمة i واحدة بترتيب تنازلي للقيمة الوسطى. في [-2, -1, 0, 1, 1, 2] مع i = 0، تجد [-2, 1, 1] عند نسخة 1 الثانية، ثم [-2, 0, 2] عند 2. اعكس ترتيب كل مجموعة قبل إضافتها إلى الإجابة. تستخدم نسختا C وR مصفوفة مفهرسة بالقيم لتحديد القيم التي تمت رؤيتها بدلًا من مجموعة تجزئة، وهذا ممكن لأن كل قيمة تقع ضمن ±10^5.

يمكن للترتيب التصاعدي أن يحل محل المجموعة. ثبّت nums[i]، وضع lo عند i+1 وhi عند الفهرس الأخير، وانظر إلى nums[i] + nums[lo] + nums[hi]. إذا كان المجموع أقل من 0، فأنت بحاجة إلى قيمة أكبر، لذا يتحرك lo إلى اليمين. وإذا كان أكبر من 0، فأنت بحاجة إلى قيمة أصغر، لذا يتحرك hi إلى اليسار. وعندما يساوي المجموع 0 تمامًا، سجّل الثلاثية وحرّك المؤشرين معًا.

لا تضيع أي ثلاثية. عندما يكون المجموع أقل من 0، تكون nums[lo] صغيرة أكثر من اللازم حتى مع أكبر قيمة متبقية، وهي nums[hi]، لذا لا يمكنها أن تقترن بأي قيمة ما زالت ضمن النطاق، ولن يؤدي استبعادها إلى فقدان أي شيء. والحالة التي يكون فيها المجموع أكبر من 0 هي العكس: تكون nums[hi] كبيرة أكثر من اللازم حتى مع أصغر قيمة متبقية. في كل خطوة، يُستبعد عنصر واحد نهائيًا، لذا تستغرق كل قيمة من قيم i عددًا من الخطوات لا يتجاوز n، ويستغرق البحث كله O(n²)، من دون ذاكرة إضافية تتجاوز الترتيب والناتج.

خذ القائمة المرتبة [-2, -1, 0, 1, 1, 2]. عندما تكون i = 0 (القيمة -2)، يبدأ lo عند -1 وhi عند 2: المجموع هو -1، لذا يتحرك lo إلى 0. الآن -2 + 0 + 2 = 0، لذا تسجّل [-2, 0, 2] ويصل المؤشران إلى قيمتي 1، فتكون النتيجة [-2, 1, 1]. عندما تكون i = 1 (القيمة -1)، يعطي 0 و2 مجموعًا يساوي 1، لذا يتحرك hi إلى قيمة 1 الثانية، ويكون -1 + 0 + 1 = 0، فتُسجّل [-1, 0, 1]. لا تجد القيمة 0 عند i = 2 أي شيء، وعند i = 3 تكون القيمة موجبة، لذا يتوقف البحث.

للقيم المكررة قاعدتان. تخطَّ قيمة i إذا كانت تساوي القيمة التي قبلها. بعد العثور على تطابق، حرّك lo متجاوزًا النسخ المطابقة للقيمة التي استخدمها. لا يحتاج hi إلى قاعدة خاصة به: عندما يكون lo عند قيمة أكبر، تؤدي نسخة من nums[hi] القديمة الآن إلى مجموع أكبر من 0، فتتحرك بعيدًا تلقائيًا. وبما أن i يمر على القيم المميزة بترتيب تصاعدي، وأن lo يتحرك إلى اليمين فقط، تخرج الثلاثيات مرتبة.