ຊອກເອທັງ ໝົດ ສາມໃບດ້ວຍເລກລວມສູນ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon GE Healthcare ກູໂກ hike
Array Hash ຊອກຫາ ຮຽງລໍາດັບ

ບັນຫາ "ຊອກຫາສາມຕົວເລກທັງ ໝົດ ດ້ວຍເລກລວມສູນ" ລະບຸວ່າທ່ານຖືກຈັດໃຫ້ມີຕົວເລກບວກແລະລົບທັງສອງ. ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາຂໍໃຫ້ຄົ້ນຫາສາມລ່ຽມ ຄຳ ທີ່ມີຜົນບວກເທົ່າກັບ 0.

ຊອກເອທັງ ໝົດ ສາມໃບດ້ວຍເລກລວມສູນ

ຍົກຕົວຢ່າງ

arr[] = {0,-2,1,3,2,-1}
(-2 -1  3) (-2 0  2) (-1 0  1)

ຄໍາອະທິບາຍ

ເຫຼົ່ານີ້ແມ່ນສາມສ່ວນຂອງ ຈຳ ນວນດັ່ງກ່າວແມ່ນ 0.

(-2 + -1 + 3 = 0) (-2 + 0 + 2 = 0) (+1+ 0 + 1 = 0)

arr[] = {2,4,-5,-1,3}
(-5 2 3)

ຄໍາອະທິບາຍ

ນີ້ແມ່ນສາມສ່ວນຂອງຕົວເລກທີ່ຕົວເລກລວມແມ່ນ 0 ⇒ -5 + 2 + 3 = 0

ລະບົບວິເຄາະ

  1. ການຈັດລຽງ ອາເລທີ່ໃຫ້.
  2. ຕັ້ງຄ່າ ບົວບານ ຕົວແປ isFound ທີ່ບໍ່ຖືກຕ້ອງ.
  3. Looping ຈາກ i = 0 ເຖິງ i
    1. ທີ່ກໍານົດໄວ້ fir = i + 1, ວິນາທີ = n-1 ແລະຕົວແປອື່ນ x ກັບອົງປະກອບຂບວນປັດຈຸບັນ.
    2. ໃນຂະນະທີ່ fir
      1. ກວດເບິ່ງວ່າສາມຂອງອົງປະກອບຮ່ວມກັນປະກອບເປັນຜົນບວກຂອງ 0.
        1. ຖ້າຖືກຕ້ອງ, ຫຼັງຈາກນັ້ນພິມທັງສາມເລກແລະ ກຳ ນົດໃຫ້ຖືກຕ້ອງຕາມຄວາມຈິງ.
      2. ກວດເບິ່ງວ່າຜົນລວມຂອງສາມອົງປະກອບ (ປັດຈຸບັນອາເລ) ນ້ອຍກວ່າ 0.
        1. ຖ້າຖືກຕ້ອງ, ຫຼັງຈາກນັ້ນເພີ່ມມູນຄ່າຂອງ fir ໂດຍ 1.
      3. ກວດເບິ່ງບ່ອນອື່ນຖ້າຜົນລວມຂອງສາມອົງປະກອບໃຫຍ່ກວ່າ 0.
          1. ຖ້າຖືກຕ້ອງ, ຫຼັງຈາກນັ້ນຫຼຸດຄ່າຂອງວິນາທີລົງ 1.
  4. ກວດເບິ່ງວ່າ isFound ຍັງບໍ່ຖືກຕ້ອງ, ນັ້ນ ໝາຍ ຄວາມວ່າບໍ່ສາມາດສ້າງຕັ້ງສາມເທັກໄດ້.

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ຮັບການຈັດແຈງ. ຫຼັງຈາກນັ້ນ, ພວກເຮົາຖືກຂໍໃຫ້ ກຳ ນົດສາມສ່ວນທີ່ສາມາດປະກອບດ້ວຍຕົວເລກທີ່ໃຫ້ໄວ້ໃນອາເລເຊິ່ງຜົນລວມຂອງມັນແມ່ນ 0. ພວກເຮົາ ກຳ ລັງຈະໃຊ້ loop ຮັງ. ສູດການຄິດໄລ່ນີ້ສາມາດເຮັດວຽກໄດ້ໃນພື້ນທີ່ຄົງທີ່. ຫນ້າທໍາອິດ, ພວກເຮົາກໍາລັງຈະຈັດຮຽງແຖວ. ວິທີນີ້ພວກເຮົາສາມາດ ນຳ ໃຊ້ເທັກນິກສອງຕົວຊີ້. ພວກເຮົາຈະປະກາດຕົວແປ Boolean ໜຶ່ງ ດຽວແລະ ກຳ ນົດຄ່າຂອງມັນບໍ່ຖືກຕ້ອງໃນຕອນ ທຳ ອິດ. ນີ້ແມ່ນເພື່ອຮັບປະກັນວ່າພວກເຮົາຈະບໍ່ພົບສາມສ່ວນສາມທີ່ມີສ່ວນປະກອບລວມເຖິງ 0, ມູນຄ່າຂອງ isFound ຍັງຄົງບໍ່ຖືກຕ້ອງ. ຫຼັງຈາກນັ້ນພວກເຮົາ ກຳ ລັງຈະປັບປຸງມັນໃຫ້ເປັນຄວາມຈິງທຸກໆຄັ້ງທີ່ພວກເຮົາພົບເຫັນສາມຂາ. ສະນັ້ນດ້ວຍສິ່ງດັ່ງກ່າວ, ພວກເຮົາສາມາດສະຫຼຸບໄດ້ວ່າບໍ່ມີສາມລິງຄູ່.

ພວກເຮົາຈະຈັດຮຽງແຖວກ່ອນ, ໃນວົງຈອນຮັງ. ຫຼັງຈາກນັ້ນ, ພວກເຮົາກໍ່ຍ້າຍແຖວໄປເຖິງ n-1. ພວກເຮົາຈະ ກຳ ນົດຄ່າເລີ່ມຕົ້ນຄື i + 1, ຄ່າສຸດທ້າຍໃຫ້ n-1, ແລະ x ກັບຄ່າປັດຈຸບັນໃນວົງນອກ. ໃນວົງແຫວນພາຍໃນພວກເຮົາຈະຕີມູນຄ່າຂອງອາເລ, ແລະກວດເບິ່ງວ່າຜົນລວມຂອງທັງ ໝົດ ຂອງສາມອົງປະກອບ (x + arr [fir] + arr [sec]) ແມ່ນເທົ່າກັບ 0 ຫຼືບໍ່. ຖ້າມັນພົບວ່າ 0, ນັ້ນ ໝາຍ ຄວາມວ່າພວກເຮົາໄດ້ພົບຄູ່ ທຳ ອິດແລະພິມຄ່າທັງ ໝົດ ໃນປະຈຸບັນຂອງອາເລແລະ ກຳ ນົດຄ່າ isFound ໃຫ້ເປັນຄວາມຈິງ.

ນີ້ຊີ້ໃຫ້ເຫັນວ່າພວກເຮົາໄດ້ພົບເຫັນຄູ່ ໜຶ່ງ. ຖ້າຜົນລວມຂອງ triplet ບໍ່ເທົ່າກັບ 0. ພວກເຮົາກວດເບິ່ງວ່າຜົນລວມຂອງສາມອົງປະກອບປັດຈຸບັນແມ່ນ ໜ້ອຍ ກວ່າ 0. ຖ້າຜົນລວມ ໜ້ອຍ ກວ່າ 0. ພວກເຮົາເພີ່ມ fir, ໝາຍ ຄວາມວ່າຄ່າເລີ່ມຕົ້ນຂອງພວກເຮົາເພີ່ມຂື້ນ. ຖ້າສະພາບບໍ່ພໍໃຈ. ພວກເຮົາກວດເບິ່ງວ່າຜົນລວມໃຫຍ່ກ່ວາ 0. ຖ້າແມ່ນ, ຫຼັງຈາກນັ້ນຫຼຸດລົງວິນາທີ.

ດ້ວຍວິທີນີ້, ພວກເຮົາ ກຳ ລັງຈະຄົ້ນຫາທຸກສາມຕົວທີ່ເປັນໄປໄດ້ເຊິ່ງສາມາດຈະເປັນ 0.

ລະຫັດ C ++ ເພື່ອຊອກຫາສາມສ່ວນພ້ອມດ້ວຍເລກລວມສູນ

#include<iostream>
#include<algorithm>

using namespace std;

void getTripletZero(int arr[], int n)
{
    bool isFound = false;
    sort(arr, arr+n);

    for (int i=0; i<n-1; i++)
    {
        int fir = i + 1;
        int sec = n - 1;
        int x = arr[i];
        while (fir < sec)
        {
            if (x + arr[fir] + arr[sec] == 0)
            {
                cout<<"("<<x<<" "<<arr[fir]<<" "<< arr[sec]<<")"<<endl;
                fir++;
                sec--;
                isFound = true;
            }
            else if (x + arr[fir] + arr[sec] < 0)
                fir++;
            else
                sec--;
        }
    }
    if (isFound == false)
        cout << " There is no triplet can be formed..!" << endl;
}
int main()
{
    int arr[] = {0,-2,1,3,2,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    getTripletZero(arr, n);
    return 0;
}
(-2 -1 3)
(-2 0 2)
(-1 0 1)

ລະຫັດ Java ເພື່ອຊອກຫາສາມສ່ວນພ້ອມດ້ວຍເລກລວມສູນ

import java.util.Arrays;

class TripletSumzero
{
    public static void getTripletZero(int arr[], int n)
    {
        boolean isFound = false;

        Arrays.sort(arr);

        for (int i=0; i<n-1; i++)
        {
            int fir = i + 1;
            int sec = n - 1;
            int x = arr[i];
            while (fir < sec)
            {
                if (x + arr[fir] + arr[sec] == 0)
                {
                    System.out.println("(" + x + " "+arr[fir]+ " "+" "+arr[sec]+")");
                    fir++;
                    sec--;
                    isFound = true;
                }
                else if (x + arr[fir] + arr[sec] < 0)
                    fir++;
                else
                    sec--;
            }
        }
        if (isFound == false)
            System.out.println(" There is no triplet can be formed..!");
    }
    public static void main (String[] args)
    {
        int arr[] = {0,-2,1,3,2,-1};
        int n =arr.length;
        getTripletZero(arr, n);
    }
}
(-2 -1  3)
(-2 0  2)
(-1 0  1)

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

ໂອ (ນ2) ບ່ອນທີ່ "n"  ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ເນື່ອງຈາກວ່າພວກເຮົາ ກຳ ລັງ ນຳ ໃຊ້ເທັກນິກສອງຕົວທີ່ປະກອບສ່ວນໃຫ້ເວລາ O (n). ແຕ່ເຕັກນິກແມ່ນຕົວເອງໃຊ້ໃນເວລາ O (n). ດັ່ງນັ້ນຈຶ່ງເຮັດໃຫ້ລະບົບ algorithm ດຳ ເນີນການໃນເວລາ O (n ^ 2).

ຄວາມສັບສົນໃນອະວະກາດ

O (1) ຍ້ອນວ່າບໍ່ ຈຳ ເປັນຕ້ອງມີພື້ນທີ່ພິເສດ.