总计给定值的所有唯一三元组


难度级别 中等
经常问 ol石 亚马逊 狂徒
排列 哈希 搜索

我们给了 排列 整数和给定数字称为“和”。 问题陈述要求找出加起来等于给定数字“和”的三元组。

使用案列

输入:

arr [] = {3,5,7,5,6,1}

总和= 16

输出:

(3,7,6),(5,5,6)

说明:

三元组等于给定的总和.

输入:

arr [] = {3,4,1,5,4}

总和= 20

输出:

没有给定数量的三胞胎

算法

  1. 对给定的数组进行排序。
  2. 将布尔变量isFound设置为false。
  3. 当我= 0到我
    1. 设置j = i + 1,k = n-1。
    2. 当j <k
      1. 检查三个元素的总和是否等于给定的总和。
        1. 如果为true,则打印所有三个数字并将isFound设置为true。
      2. 否则,检查三个元素的总和是否大于总和。
        1. 如果为true,则将k的值减小1。
      3. 检查三个元素(当前数组元素)的总和是否小于总和。
        1. 如果为true,则将j的值增加1。
  4. 检查isFound是否仍然为false,得出无法形成三元组的结论。

说明

我们会 分类 该数组首先使值按升序排列,因为我们将使用 二进制搜索 方法,一点点。 我们将声明一个 布尔变量 并首先将其值设置为false,一旦找到三元组,我们将对其进行更新。 这是为了确保如果我们找不到元素总数为给定数的三元组,则isFound值保持原样,只有在找到三元组时才将其更新为true,因此,我们可以得出结论,没有找到三元组。

对数组进行排序后,从嵌套循环开始,我们将遍历数组直到长度为n-1。 将其中一个变量值设置为i + 1,将另一个值设置为n-1。 在内部循环中,我们将遍历数组的所有值,并检查给定的数字“ sum”是否等于三个当前数组元素的总和(arr [i] + arr [j] + arr [k ])是否相等。 如果条件满足,我们将打印数组的所有当前值,并将isFound值设置为true,以确保我们不应该返回假值。

如果数组的三个当前值的总和不等于给定的数字,我们将检查三个当前元素的总和是否小于给定的总和,如果小于总和,我们将增加该值的j,表示我们的左指针,该指针从左开始 遍历 是增加,并且如果还不满足此条件,我们将检查总和是否大于总和。如果为true,则将减少k的值。

它将继续直到遍历数组的所有值。 然后,我们将返回isFound值,如果找到任何三元组,则可以将其返回true;如果找不到任何三元组,则可以将其返回false。

实施

总计为给定值的所有唯一三元组的C ++程序

#include<iostream>
#include<algorithm>

using namespace std;

int getTripletOfSum(int arr[], int n, int sum)
{
    int i, j, k;
    bool isFound=false;
    sort(arr, arr + n);
    for(i = 0; i < n - 2; i++)
    {
        j = i + 1;
        k = n - 1;

        while(j < k)
        {
            if(arr[i] + arr[j] + arr[k] == sum)
            {
                cout<<"["<<arr[i]<<" "<<arr[j]<<" "<<arr[k]<<"]"<<endl;
                j++;
                k--;
                isFound=true;
            }
            else if(arr[i] + arr[j] + arr[k] > sum)
                k--;
            else
                j++;
        }
    }
    return isFound;
}
int main()
{
    int nums[] = {3,5,7,5,6,1};
    int n = sizeof(nums) / sizeof(nums[0]);
    int sum = 16;
    if(!getTripletOfSum(nums, n, sum))
        cout << "There are no triplets that can be formed with the given number";

    return 0;
}
[3 6 7]
[5 5 6]

总计为给定值的所有唯一三元组的Java程序

import java.util.Arrays;

public class TripletsWithSum
{
    public static boolean getTripletOfSum(int arr[], int sum)
    {
        Arrays.sort(arr);

        boolean isFound=false;

        for (int i = 0; i < arr.length - 2; i++)
        {
            int j = i + 1;
            int k = arr.length - 1;
            while (j < k)
            {
                if (arr[i] + arr[j] + arr[k] == sum)
                {
                    System.out.println("["+arr[i] + " " + arr[j] +" " +arr[k]+"]");
                    j++;
                    k--;
                    isFound=true;
                }
                else if (arr[i] + arr[j] + arr[k] < sum)
                    j++;

                else
                    k--;
            }
        }
        return isFound;
    }
    public static void main(String[] args)
    {
        int arr[] = {3,5,7,5,6,1};
        int sum = 16;
        if (!getTripletOfSum(arr, sum))
        {
            System.out.println("There are no triplets that can be formed with the given number");
        }
    }
}
[3 6 7]
[5 5 6]

求和为给定值的所有唯一三元组的复杂度分析

时间复杂度

2哪里 “ n” 是数组中元素的数量。

空间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。