所有唯一三元組的總和為給定值  


難度級別 中烘焙
經常問 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” 是數組中元素的數量。