四数之和 - 统计数组中和为目标值的四元组

给定一个数组 INLINECODEd2480834 和一个目标值 INLINECODEf3d84a82，我们的任务是找出给定数组中存在的四元组数量，使得它们的和等于给定的目标值。

示例：

> 输入： arr[] = [1, 5, 3, 1, 2, 10], target = 20

> 输出： 1

> 解释： 唯一满足条件的四元组是 arr[1] + arr[2] + arr[4] + arr[5] = 5 + 3 + 2 + 10 = 20。

>

> 输入： arr[] = [1, 1, 1, 1, 1], target = 4

> 输出： 5

> 解释：

> arr[0] + arr[1] + arr[2] + arr[3] = 4

> arr[0] + arr[1] + arr[3] + arr[4] = 4

> arr[0] + arr[1] + arr[2] + arr[4] = 4

> arr[0] + arr[2] + arr[3] + arr[4] = 4

> arr[1] + arr[2] + arr[3] + arr[4] = 4

>

> 输入： arr = [4, 3, -13, 3], target = -3

> 输出： 1

> 解释： 只有 1 个和为 -3 的四元组，即 [4, 3, -13, 3]。

目录

• 朴素方法 – O(n^4) 时间复杂度和 O(1) 空间复杂度
• 更好的方法 – O(n^3) 时间复杂度和 O(n) 空间复杂度
• 高效方法 – O(n^2) 时间复杂度和 O(n^2) 空间复杂度

朴素方法 – O(n^4) 时间复杂度和 O(1) 空间复杂度

我们的思路是从给定的数组中生成所有可能的长度为 4 的组合。对于每一个四元组，如果它们的和等于目标值，我们就将计数器加 1。

C++

#include 
#include 
using namespace std;

// 返回和为目标值的四元组数量的函数
int countSum(vector& arr, int target) {
    int n = arr.size(); 
    int count = 0;      

    // 遍历所有可能的四元组
    for (int i = 0; i < n - 3; i++) {
        for (int j = i + 1; j < n - 2; j++) {
            for (int k = j + 1; k < n - 1; k++) {
                for (int l = k + 1; l < n; l++) {                  
                    if (arr[i] + arr[j] + arr[k] + arr[l] == target) {
                        count++;
                    }
                }
            }
        }
    }

    return count; 
}

int main() {
    vector arr = {1, 1, 1, 1, 1};
    int target = 4;
    cout << countSum(arr, target) << endl;
    return 0;
}
    

C

#include 

// 返回和为目标值的四元组数量的函数
int countSum(int arr[], int n, int target) {
    int count = 0;

    // 遍历所有可能的四元组
    for (int i = 0; i < n - 3; i++) {
        for (int j = i + 1; j < n - 2; j++) {
            for (int k = j + 1; k < n - 1; k++) {
                for (int l = k + 1; l < n; l++) {
                    if (arr[i] + arr[j] + arr[k] + arr[l] == target) {
                        count++;
                    }
                }
            }
        }
    }

    return count;
}

// 主函数
int main() {
    int arr[] = {1, 1, 1, 1, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 4;
    printf("%d
", countSum(arr, n, target));
    return 0;
}
    

Java

import java.util.*;

class GfG {

    // 返回和为目标值的四元组数量的函数
    static int countSum(int[] arr, int target) {
        int n = arr.length;
        int count = 0;

        // 遍历所有可能的四元组
        for (int i = 0; i < n - 3; i++) {
            for (int j = i + 1; j < n - 2; j++) {
                for (int k = j + 1; k < n - 1; k++) {
                    for (int l = k + 1; l < n; l++) {
                        if (arr[i] + arr[j] + arr[k] + arr[l] == target) {
                            count++;
                        }
                    }
                }
            }
        }

        return count;
    }

    // 主函数
    public static void main(String[] args) {
        int[] arr = {1, 1, 1, 1, 1};
        int target = 4;
        System.out.println(countSum(arr, target));
    }
}
    

Python

# 返回和为目标值的四元组数量的函数
def countSum(arr, target):
    n = len(arr)
    count = 0

    # 遍历所有可能的四元组
    for i in range(n - 3):
        for j in range(i + 1, n - 2):
            for k in range(j + 1, n - 1):
                for l in range(k + 1, n):
                    if arr[i] + arr[j] + arr[k] + arr[l] == target:
                        count += 1
    return count

if __name__ == "__main__":
    arr = [1, 1, 1, 1, 1]
    target = 4
    print(countSum(arr, target))
    

C#

“`csharp

using System;

class GfG {

// 返回和为目标值的四元组数量的函数

static int countSum(int[] arr, int target) {

int n = arr.Length;

int count = 0;

// 遍历所有可能的四元组

for (int i = 0; i < n – 3; i++) {

for (int j = i + 1; j < n – 2; j++) {

for (int k = j + 1; k < n – 1; k++) {