从三个不同的数组中找出三个元素,使得a + b + c =和


难度级别 中等
经常问 亚马逊 Databricks 指令 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)的时间复杂度