找到所有零和的三元組


難度級別
經常問 亞馬遜 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)時間內運行。

空間複雜度

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