ຊອກຫາສາມອົງປະກອບຈາກສາມອາຄານທີ່ແຕກຕ່າງກັນດັ່ງກ່າວວ່າ a + b + c = ຜົນລວມ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon ຖານຂໍ້ມູນ Directi JP Morgan Taxi4Sure Twilio Zoho
Array Hash ແຮກ

ສາມ Sum ແມ່ນປັນຫາທີ່ຜູ້ ສຳ ພາດມັກຮັກ. ມັນເປັນບັນຫາທີ່ຂ້າພະເຈົ້າຖືກຖາມໃນລະຫວ່າງການເປັນ Amazon ການ ສຳ ພາດ. ສະນັ້ນ, ໂດຍບໍ່ເສຍເວລາອີກຕໍ່ໄປໃຫ້ພວກເຮົາເຂົ້າຫາປັນຫາ. ຂບວນທີ່ມີທັງຕົວເລກບວກແລະລົບ. ສາມຕົວເລກທີ່ນັບເປັນເລກສູນ / ສາມາດແກ້ໄຂໄດ້, ເພື່ອສະຫຼຸບໃສ່ຕົວເລກໃດ ໜຶ່ງ ຫຼືຊອກຫາສາມອົງປະກອບຈາກສາມອາຄານທີ່ແຕກຕ່າງກັນເຊັ່ນວ່າ a + b + c = sum.

ຍົກຕົວຢ່າງ

ການປ້ອນຂໍ້ມູນ

[-2,0,1,1,2]

ຜົນຜະລິດ

[[-2,0,2], [- 2,1,1]]

ຈະແກ້ໄຂແນວໃດ?

ກ່ອນທີ່ມັນຈະກາຍເປັນຄວາມເຈັບປວດໃຫຍ່ກວ່າເກົ່າ ສຳ ລັບຜູ້ອ່ານຂອງຂ້ອຍ. ຂໍໃຫ້ຂ້ອຍແລ່ນຜ່ານ pseudocode ຂະ ໜາດ ນ້ອຍທີ່ສະແດງໃຫ້ເຫັນຄືກັນ. ຂັ້ນຕອນທີໂດຍຂັ້ນຕອນ:

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

ລະຫັດ Java ສຳ ລັບສາມ Sum

class Solution 
{
    public List<List<Integer>> threeSum(int[] nums) 
    {
        Arrays.sort(nums);
        if(nums.length<3)
            return new ArrayList<>();
        Set<List<Integer>>lisa=new HashSet<>();
        for(int i=0;i<nums.length;i++)
        {
            int start=i+1;
            int end=nums.length-1;
            while(end>start)
            {
                int sum=nums[i]+nums[start]+nums[end];
                if(sum==0)
                {
                    List<Integer>cur=new ArrayList<Integer>();
                    cur.add(nums[i]);
                    cur.add(nums[start]);
                    cur.add(nums[end]);
                    lisa.add(cur);
                    end--;
                    start++;
                }
                else if(sum>0)
                    end--;
                else if(sum<0)
                    start++;
            }
        }
        return new ArrayList<>(lisa);
    }
}

ລະຫັດ C ++ ສຳ ລັບສາມ Sum

class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        sort(nums.begin(),nums.end());
        vector<vector<int>>ans;
        set<vector<int>>lisa;
        for(int i=0;i<nums.size();i++)
        {
            int start=i+1;
            int end=nums.size()-1;
            while(end>start)
            {
                int sum=nums[i]+nums[start]+nums[end];
                if(sum==0)
                {
                    lisa.insert({nums[i],nums[start],nums[end]}); 
                    end--;
                    start++;
                }
                else if(sum>0)
                    end--;
                else if(sum<0)
                    start++;
            }
        }
        for(auto x:lisa)
        {
            ans.push_back(x);
        }
        return ans;
    }
};

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

ຄວາມສັບສົນຂອງເວລາ = O (n ^ 2)

ຄວາມສັບສົນໃນອະວະກາດ = O (1)

ວິທີການ?

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

  • ທຳ ອິດ, ພວກເຮົາແລ່ນຜ່ານວົງນອກເມື່ອພົບເຫັນອົງປະກອບ ທຳ ອິດທີ່ພວກເຮົາສາມາດແກ້ໄຂໄດ້.
  • ວົງໃນ.
  • ຖືເອົາອົງປະກອບ ທຳ ອິດ.
  • ຖືເອົາອົງປະກອບທີສອງຈາກທີ່ສຸດ.
  • ໃນກໍລະນີທີ່ຮ້າຍແຮງກວ່າເກົ່າ, ພວກເຮົາອາດຈະເລີ່ມຕົ້ນຍ້າຍຈາກອົງປະກອບ ທຳ ອິດໄປຫາອົງປະກອບສຸດທ້າຍ.
  • ເຊິ່ງ ນຳ ໄປສູ່ຄວາມສັບສົນເວລາຂອງ O (n ^ 2)

ການວິເຄາະຄວາມສັບສົນໃນອະວະກາດ ສຳ ລັບສາມຍອດ

  • ພວກເຮົາພຽງແຕ່ໃຊ້ຕົວແປ ຈຳ ນວນ ໜຶ່ງ ເພື່ອຕິດຕາມ.
  • ດັ່ງນັ້ນ, ຈຶ່ງ ນຳ ພາຄວາມສັບສົນໃນອະວະກາດໃຫ້ O (1)

Tweak ຂະ ໜາດ ນ້ອຍ

ຈະເປັນແນວໃດຖ້າພວກເຮົາປ່ຽນ ໜ່ວຍ ເກັບມ້ຽນຂອງບັນຫາ Three Sum. ປະຫລາດໃຈ!?

ບໍ່​ມີ​ຫຍັງ​ຫລາຍ. ພວກເຮົາພຽງແຕ່ຈະ ນຳ ເອົາສາມຂອດທີ່ແຕກຕ່າງກັນກ່ວາ ໜຶ່ງ ແຜ່ນດຽວ. ໃນກໍລະນີທີ່ທ່ານຍັງບໍ່ທັນໄດ້ຮັບ. ຂ້າພະເຈົ້າຂໍ ນຳ ສະ ເໜີ ກໍລະນີທົດສອບຕົວຢ່າງ.

ການປ້ອນຂໍ້ມູນ

Array1 = {1, 2, 3, 4, 5}

Array2 = {2, 3, 6, 1, 2}

Array3 = {3, 2, 4, 5, -6}

ຜົນຜະລິດ

YES

ນີ້ແມ່ນຮູບພາບທີ່ສະແດງໃຫ້ເຫັນເຖິງສາມຂັ້ນທີ່ເປັນໄປໄດ້

ສາມ Sum

ວິທີການເຂົ້າຫາບັນຫາ

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

ລະຫັດ Java ສຳ ລັບສາມ Sum

public class Main
{
    public static boolean Three(int a1[],int a2[],int a3[])
    {
        Set<Integer>store=new HashSet<Integer>();
        Set<ArrayList<Integer>>lisa=new HashSet<>();
        for(int i=0;i<a2.length;i++)
        {
            for(int j=0;j<a3.length;j++)
                store.add(a2[i]+a3[j]);
        }
        for(int i=0;i<a1.length;i++)
        {
            if(store.contains(-a1[i]))
            {
                return true;
            }
        }
        return false;
    }
    public static void main (String[] args) 
    { 
        int a1[] = { 1 , 2 , 3 , 4 , 5 }; 
        int a2[] = { -2 , 3 , 6 , 1 , 2 }; 
        int a3[] = { 3 , 2 , -4 , 5 , -6 }; 
          
        int n1 = a1.length; 
        int n2 = a2.length; 
        int n3 = a3.length; 
          
        System.out.println(Three(a1, a2, a3));
    } 
}

ລະຫັດ C ++ ສຳ ລັບສາມ Sum

bool Three(int a1[],int a2[],int a3[])
    {
    int n1 = sizeof(a1) / sizeof(a1[0]); 
    int n2 = sizeof(a2) / sizeof(a2[0]); 
    int n3 = sizeof(a3) / sizeof(a3[0]); 
    set<int>store;
    for(int i=0;i<n2;i++)
    {
        for(int j=0;j<n3;j++)
            store.insert(a2[i]+a3[j]);
    }
    for(int i=0;i<n1;i++)
    {
        if(store.find(-a1[i])!=store.end())
        {
            return true;
        }
    }
    return false;
}
int main() 
{ 
    int a1[] = { 1 , 2 , 3 , 4 , 5 }; 
    int a2[] = { 2 , 3 , 6 , 1 , 2 }; 
    int a3[] = { 3 , 2 , 4 , 5 , 6 }; 
    cout<<Three(a1, a2, a3);
  
    return 0; 
}

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

ຄວາມສັບສົນຂອງເວລາ = O (n ^ 2)

ວິທີການ?

  • ພວກເຮົາດໍາເນີນການ loop ນອກເພື່ອຊອກຫາອົງປະກອບຈາກແຖວທີສອງ.
  • ໃນວົງຮອບພາຍໃນ, ພວກເຮົາເພີ່ມອົງປະກອບ ໜຶ່ງ ຈາກແຖວທີສາມໄປຫາອົງປະກອບ array ທີສອງ.
  • ຄວາມສັບສົນຂອງເວລາທີ່ເກີດຂື້ນຈົນເຖິງດຽວນີ້ແມ່ນ O (n ^ 2).
  • loop ຕໍ່ໄປກວດເບິ່ງອົງປະກອບຈາກແຖວ ທຳ ອິດ
  • ຄວາມສັບສົນຂອງເວລາ ສຳ ລັບ loop ນີ້ = O (1)
  • ຄວາມສັບສົນສຸດທ້າຍຈົນເຖິງດຽວນີ້ = O (n ^ 2) + O (1) = O (n ^ 2)

ຄວາມສັບສົນໃນອະວະກາດ = O (n)

ວິທີການ?

  • ພວກເຮົາໃຊ້ຊຸດເພື່ອເກັບສ່ວນປະກອບທັງ ໝົດ
  • ນີ້ເຮັດໃຫ້ເວລາສັບສົນຂອງ O (n)