Подсчитать количество троек в массиве с суммой в диапазоне [a, b]

Опубликовано: 16 Января, 2022

Учитывая массив различных целых чисел и диапазон [a, b], задача состоит в том, чтобы подсчитать количество троек, сумма которых находится в диапазоне [a, b].
Примеры:

 Ввод: arr [] = {8, 3, 5, 2}
        диапазон = [7, 11]
Выход: 1
Есть только одна тройка {2, 3, 5}
имея сумму 10 в диапазоне [7, 11].

Ввод: arr [] = {2, 7, 5, 3, 8, 4, 1, 9}
        диапазон = [8, 16]
Выход: 36

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

A naive approach is to run three loops to consider all the triplets one by one. Find the sum of each triplet and increment the count if the sum lies in a given range [a, b].
Below is the implementation of the above approach:
 

C++

// C++ program to count triplets with
// sum that lies in given range [a, b].
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to count triplets
int countTriplets(int arr[], int n, int a, int b)
{
    // Initialize result
    int ans = 0;
 
    // Fix the first element as A[i]
    for (int i = 0; i < n - 2; i++) {
 
        // Fix the second element as A[j]
        for (int j = i + 1; j < n - 1; j++) {
 
            // Now look for the third number
            for (int k = j + 1; k < n; k++)
 
                if (arr[i] + arr[j] + arr[k] >= a
                    && arr[i] + arr[j] + arr[k] <= b)
                    ans++;
        }
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 7, 5, 3, 8, 4, 1, 9 };
    int n = sizeof arr / sizeof arr[0];
    int a = 8, b = 16;
    cout << countTriplets(arr, n, a, b) << endl;
    return 0;
}

Java

// Java program to count triplets
// with sum that lies in given
// range [a, b].
import java.util.*;
 
class GFG
{
     
// Function to count triplets
public static int countTriplets(int []arr, int n,
                                int a, int b)
{
    // Initialize result
    int ans = 0;
 
    // Fix the first
    // element as A[i]
    for (int i = 0; i < n - 2; i++)
    {
 
        // Fix the second
        // element as A[j]
        for (int j = i + 1; j < n - 1; j++)
        {
 
            // Now look for the
            // third number
            for (int k = j + 1; k < n; k++)
            {
                if (arr[i] + arr[j] + arr[k] >= a &&
                    arr[i] + arr[j] + arr[k] <= b)
                    {ans++;}
            }
        }
    }
 
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 2, 7, 5, 3, 8, 4, 1, 9 };
    int n = arr.length;
    int a = 8, b = 16;
    System.out.println("" + countTriplets(arr, n,
                                        a, b));
}
}
 
// This code is contributed
// by Harshit Saini

Python3

# Python3 program to count
# triplets with sum that
# lies in given range [a, b].
 
# Function to count triplets
def countTriplets(arr, n, a, b):
     
    # Initialize result
    ans = 0
 
    # Fix the first
    # element as A[i]
    for i in range(0, n - 2):
         
        # Fix the second
        # element as A[j]
        for j in range(i + 1, n - 1):
 
            # Now look for
            # the third number
            for k in range(j + 1, n):
 
                if ((arr[i] + arr[j] + arr[k] >= a)
                and (arr[i] + arr[j] + arr[k] <= b)):
                        ans += 1
                         
    return ans
 
# Driver code
if __name__ == "__main__":
     
    arr = [ 2, 7, 5, 3, 8, 4, 1, 9 ]
    n = len(arr)
    a = 8; b = 16
    print(countTriplets(arr, n, a, b))
 
# This code is contributed
# by Harshit Saini

C#

// C# program to count triplets
// with sum that lies in given
// range [a, b].
using System;
 
class GFG
{
     
// Function to count triplets
public static int countTriplets(int []arr, int n,
                                int a, int b)
{
    // Initialize result
    int ans = 0;
 
    // Fix the first
    // element as A[i]
    for (int i = 0;
            i < n - 2; i++)
    {
 
        // Fix the second
        // element as A[j]
        for (int j = i + 1;
                j < n - 1; j++)
        {
 
            // Now look for the
            // third number
            for (int k = j + 1;
                    k < n; k++)
            {
                if (arr[i] + arr[j] + arr[k] >= a &&
                    arr[i] + arr[j] + arr[k] <= b)
                    {ans++;}
            }
        }
    }
 
    return ans;
}
 
// Driver Code
public static void Main()
{
    int[] arr = {2, 7, 5, 3, 8, 4, 1, 9};
    int n = arr.Length;
    int a = 8, b = 16;
    Console.WriteLine("" + countTriplets(arr, n,
                                        a, b));
}
}
 
// This code is contributed
// by Akanksha Rai(Abby_akku)

PHP

<?php
// PHP program to count triplets with
// sum that lies in given range [a, b].
 
// Function to count triplets
function countTriplets($arr, $n, $a, $b)
{
    // Initialize result
    $ans = 0;
 
    // Fix the first element as A[i]
    for ($i = 0; $i < $n - 2; $i++)
    {
 
        // Fix the second element as A[j]
        for ($j = $i + 1; $j < $n - 1; $j++)
        {
 
            // Now look for the third number
            for ($k = $j + 1; $k < $n; $k++)
 
                if ($arr[$i] + $arr[$j] + $arr[$k] >= $a &&
                    $arr[$i] + $arr[$j] + $arr[$k] <= $b)
                    $ans++;
        }
    }
 
    return $ans;
}
 
// Driver Code
$arr = array( 2, 7, 5, 3, 8, 4, 1, 9 );
$n = sizeof($arr);
$a = 8; $b = 16;
echo countTriplets($arr, $n, $a, $b) . " ";
 
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>

Javascript

<script>
 
 
// Javascript program to count triplets with
// sum that lies in given range [a, b].
 
// Function to count triplets
function countTriplets( arr, n, a, b)
{
    // Initialize result
    var ans = 0;
 
    // Fix the first element as A[i]
    for (var i = 0; i < n - 2; i++) {
 
        // Fix the second element as A[j]
        for (var j = i + 1; j < n - 1; j++) {
 
            // Now look for the third number
            for (var k = j + 1; k < n; k++)
 
                if (arr[i] + arr[j] + arr[k] >= a
                    && arr[i] + arr[j] + arr[k] <= b)
                    ans++;
        }
    }
 
    return ans;
}
 
// Driver Code
var arr = [ 2, 7, 5, 3, 8, 4, 1, 9 ];
var n = arr.length;
var a = 8, b = 16;
document.write( countTriplets(arr, n, a, b) );
 
 
</script>
Output: 
36

 

Временная сложность: O (n 3 )
Эффективное решение - сначала найти количество троек, сумма которых меньше или равна верхнему пределу b в диапазоне [a, b]. Это количество троек также будет включать тройки, сумма которых меньше нижнего предела a. Вычтите количество троек, сумма которых меньше a. Конечный результат - это количество троек, сумма которых находится в диапазоне [a, b].
Алгоритм следующий:

  • Find count of triplets having a sum less than or equal to b. Let this count be x.
  • Find count of triplets having a sum less than a. Let this count be y.
  • Final result is x-y.

To find the count of triplets having a sum less than or equal to the given value, refer Count triplets with sum smaller than a given value 
Below is the implementation of the above approach: 
 

C++

// C++ program to count triplets with
// sum that lies in given range [a, b].
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find count of triplets having
// sum less than or equal to val.
int countTripletsLessThan(int arr[], int n, int val)
{
    // sort the input array.
    sort(arr, arr + n);
 
    // Initialize result
    int ans = 0;
 
    int j, k;
 
    // to store sum
    int sum;
 
    // Fix the first element
    for (int i = 0; i < n - 2; i++) {
 
        // Initialize other two elements as
        // corner elements of subarray arr[j+1..k]
        j = i + 1;
        k = n - 1;
 
        // Use Meet in the Middle concept.
        while (j != k) {
            sum = arr[i] + arr[j] + arr[k];
 
            // If sum of current triplet
            // is greater, then to reduce it
            // decrease k.
            if (sum > val)
                k--;
 
            // If sum is less than or equal
            // to given value, then add
            // possible triplets (k-j) to result.
            else {
                ans += (k - j);
                j++;
            }
        }
    }
 
    return ans;
}
 
// Function to return count of triplets having
// sum in range [a, b].
int countTriplets(int arr[], int n, int a, int b)
{
 
    // to store count of triplets.
    int res;
 
    // Find count of triplets having sum less
    // than or equal to b and subtract count
    // of triplets having sum less than or
    // equal to a-1.
    res = countTripletsLessThan(arr, n, b) -
        countTripletsLessThan(arr, n, a - 1);
 
    return res;
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 7, 5, 3, 8, 4, 1, 9 };
    int n = sizeof arr / sizeof arr[0];
    int a = 8, b = 16;
    cout << countTriplets(arr, n, a, b) << endl;
    return 0;
}

Java

// Java program to count triplets
// with sum that lies in given
// range [a, b].
import java.util.*;
 
class GFG
{
// Function to find count of
// triplets having sum less
// than or equal to val.
public static int countTripletsLessThan(int []arr,
                                        int n, int val)
{
    // sort the input array.
    Arrays.sort(arr);
 
    // Initialize result
    int ans = 0;
 
    int j, k;
 
    // to store sum
    int sum;
 
    // Fix the first element
    for (int i = 0; i < n - 2; i++)
    {
 
        // Initialize other two elements
        // as corner elements of subarray
        // arr[j+1..k]
        j = i + 1;
        k = n - 1;
 
        // Use Meet in the
        // Middle concept.
        while (j != k)
        {
            sum = arr[i] + arr[j] + arr[k];
 
            // If sum of current triplet
            // is greater, then to reduce it
            // decrease k.
            if (sum > val)
Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022
Amazon SDE Sheet: вопросы и ответы на собеседовании
12 Декабря, 2022