找到所有零和的三元組  


難度級別 中烘焙
經常問 亞馬遜 GE醫療集團 谷歌 遠足
排列 哈希 搜索 排序

問題“用零和查找所有三元組”指出給您一個包含正數和負數的數組。 問題陳述要求找出總和等於0的三元組。

找到所有零和的三元組

例  

arr[] = {0,-2,1,3,2,-1}
(-2 -1  3) (-2 0  2) (-1 0  1)

解釋

這些是三元組,其總和為0。

(-2 + -1 + 3 = 0)(-2 + 0 + 2 = 0)(-1+ 0 + 1 = 0)

arr[] = {2,4,-5,-1,3}
(-5 2 3)

解釋

這些是三元組,其數字總和為0⇒-5 + 2 + 3 = 0

算法  

  1. 分類 給定的數組。
  2. 設置 布爾 變量 被發現 虛假。
  3. 從i = 0循環到i
    1. 在你的生活中 fir = i + 1,sec = n-1 和另一個變量 x 到當前數組元素。
    2. 當冷杉
      1. 檢查三個元素是否加在一起為0。
        1. 如果為true,則打印所有三個數字並將isFound設置為true。
      2. 檢查三個元素(當前數組元素)的總和是否小於0。
        1. 如果為true,則將fir的值增加1。
      3. 否則,檢查三個元素的總和是否大於0。
          1. 如果為true,則將sec的值減小1。
  4. 檢查isFound是否仍然為false,這意味著無法形成三元組。

解釋

給我們一個數組。 然後,我們被要求確定在給定總數為0的數組中可以由給定數字形成的三元組。我們將使用嵌套循環。 該算法可以在恆定空間中工作。 首先,我們將對數組進行排序。 這樣,我們可以使用兩指針技術。 我們將聲明一個布爾變量並將其值首先設置為false。 這只是為了確保我們是否找不到元素總和為0的三元組,即 被發現 仍然是錯誤的。 然後,只要找到三元組,我們就將其更新為true。 因此,我們可以得出結論,沒有找到三重態。

也可以看看
刪除並賺取

我們將首先在嵌套循環中對數組進行排序。 然後我們遍歷數組直到n-1。 我們將在外部循環中將起始值設置為i + 1,將最後一個值設置為n-1,將x設置為當前值。 在內部循環中,我們將遍歷數組的值,並檢查所有三個元素(x + arr [fir] + arr [sec])的總和是否等於0。 如果發現它為0,則意味著我們找到了第一對,並打印了數組的所有當前值,並將isFound值設置為true。

這表明我們找到了一對。 如果三元組的總和不等於0。我們檢查三個電流元素的總和是否小於0。如果總和小於0。我們增加fir,意味著我們的起始值增加了。 如果不滿足條件。 我們檢查總和是否大於0。如果為true,則減少秒數。

這樣,我們將找到所有可能合計為0的三元組。

C ++代碼查找總和為零的所有三元組  

#include<iostream>
#include<algorithm>

using namespace std;

void getTripletZero(int arr[], int n)
{
    bool isFound = false;
    sort(arr, arr+n);

    for (int i=0; i<n-1; i++)
    {
        int fir = i + 1;
        int sec = n - 1;
        int x = arr[i];
        while (fir < sec)
        {
            if (x + arr[fir] + arr[sec] == 0)
            {
                cout<<"("<<x<<" "<<arr[fir]<<" "<< arr[sec]<<")"<<endl;
                fir++;
                sec--;
                isFound = true;
            }
            else if (x + arr[fir] + arr[sec] < 0)
                fir++;
            else
                sec--;
        }
    }
    if (isFound == false)
        cout << " There is no triplet can be formed..!" << endl;
}
int main()
{
    int arr[] = {0,-2,1,3,2,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    getTripletZero(arr, n);
    return 0;
}
(-2 -1 3)
(-2 0 2)
(-1 0 1)

Java代碼查找總和為零的所有三元組  

import java.util.Arrays;

class TripletSumzero
{
    public static void getTripletZero(int arr[], int n)
    {
        boolean isFound = false;

        Arrays.sort(arr);

        for (int i=0; i<n-1; i++)
        {
            int fir = i + 1;
            int sec = n - 1;
            int x = arr[i];
            while (fir < sec)
            {
                if (x + arr[fir] + arr[sec] == 0)
                {
                    System.out.println("(" + x + " "+arr[fir]+ " "+" "+arr[sec]+")");
                    fir++;
                    sec--;
                    isFound = true;
                }
                else if (x + arr[fir] + arr[sec] < 0)
                    fir++;
                else
                    sec--;
            }
        }
        if (isFound == false)
            System.out.println(" There is no triplet can be formed..!");
    }
    public static void main (String[] args)
    {
        int arr[] = {0,-2,1,3,2,-1};
        int n =arr.length;
        getTripletZero(arr, n);
    }
}
(-2 -1  3)
(-2 0  2)
(-1 0  1)

複雜度分析  

時間複雜度

2) 哪裡 “ n”  是數組中元素的數量。 由於我們使用的是兩個指針技術,因此會佔用O(n)的時間。 但是該技術本身用於O(n)時間。 從而使算法在O(n ^ 2)時間內運行。

也可以看看
3總和

空間複雜度

O(1) 因為不需要額外的空間。