從三個不同的數組中找出三個元素,使得a + b + c =和


難度級別
經常問 亞馬遜 數據塊 指令 JP摩根 出租車 Twilio 百會
排列 哈希 哈希

三和是面試官喜歡的一個問題。 這是我在問詢過程中親自問到的一個問題。 亞馬遜 面試。 因此,在不浪費更多時間的情況下,讓我們解決問題。 同時具有正數和負數的數組。 總計為零/的三個數字可以修改,以求和為任何整數或從不同的三個數組中找到三個元素,這樣a + b + c =和。

輸入

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

產量

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

怎麼解決呢?

在它給我的讀者帶來更大的痛苦之前。 讓我看一下小偽代碼來說明這一點。 一步步:

  • 首先 分類 數字。
  • 排序可幫助我們根據數字的大小訪問數字。
  • 其次,我們從數組中選擇一個元素。
  • 第三,我們選擇兩個元素,這些元素與第一個元素相加將得出零。
  • 如果您有Deja Vu,請允許我提出提示。
  • 求和問題。
  • 修復第一個元素後,我們將遍歷數組以查找其他兩個元素。
  • 我們有兩個目的。
  • 每當兩端的和大於期望值時,我們就會減小最終值。
  • 每當兩端的和小於期望值時,我們就會增加起始值。
  • 如果總和達到0,我們記錄元素。
  • 最後,將元素添加到集合的ArrayList中,以確保沒有重複。

三和的Java代碼

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 ++代碼

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)

一個小的調整

如果我們更改“三和”問題的存儲單位怎麼辦。 驚訝!?

沒什麼。 我們將只使用三個數組,而不是單個數組。 萬一您仍然沒有得到它。 讓我提出一個示例測試用例。

輸入

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

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

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

產量

這是突出顯示可能的三胞胎的圖像

三和

如何解決問題

  • 首先,我們嘗試從任意兩個數組中生成總和的所有可能組合。
  • 為此,我們運行兩個循環
  • 我們將所有這些組合存儲在一組中以避免重複
  • 我們檢查總和的-ve值在第三個數組中是否可用
  • 如果是,那麼我們返回是
  • 最後,即使在遍歷所有數組之後,如果我們未達到0,那麼我們返回false

三和的Java代碼

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 ++代碼

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)

怎麼樣?

  • 我們運行一個外部循環以從第二個數組中查找元素。
  • 在內部循環中,我們將第三個數組中的元素添加到第二個數組元素中。
  • 到現在為止所花費的時間複雜度為O(n ^ 2)。
  • 下一個循環檢查第一個數組中的元素
  • 此循環的時間複雜度= O(1)
  • 到目前為止的最終複雜度= O(n ^ 2)+ O(1)= O(n ^ 2)

空間複雜度= O(n)

怎麼樣?

  • 我們使用一組存儲所有元素
  • 這導致O(n)的時間複雜度