求出数组中元素的总和_在数组中找到三个元素，使其总和等于给定元素K

我不是女神ヾ 2023-03-05 05:29 5阅读 0赞

求出数组中元素的总和

**Description:**

**描述：**

Given an array of **n** elements. Find three elements such that their sum is equal to given element **K**.

给定**n个**元素的数组。 找到三个元素，使其总和等于给定元素**K。**

**Solutions:**

**解决方案：**

**Brute force method**: The brute force solution is to check if there are any elements whose sum is equal to K for any two input pair taken from the array. This solution requires to run three loops and the time complexity is much higher, **O(n3)**.

**蛮力方法** ：蛮力解决方案是检查从数组中获取的任何两个输入对是否有任何元素的总和等于K。 该解决方案需要运行三个循环，并且时间复杂度要高得多， **O(n 3 )** 。

**Advanced algorithm with lesser time complexity**

**先进的算法，时间复杂度更低**

1.	Sort the array.
    2.	for k=0:n-1 // k from 0 to n-1
    		for i=k+1, j=n-1 & i<j   //i=k+1, j= n-1 && loop till i<j
    			if( array[k]+array[i]+array[j]==K)    // if they sums to K
    				Print elements;  //then print
    			else if(array[k]+array[i]+array[j]<K) //if sum is <K
    				i=i+1; // increase i since array is sorted 
    			else //else
    				j=j-1; //decrease j
    		End for loop
    	End for loop
    3.	If no elements are found print no such elements present.

**Time complexity:** **O(n2)** ( for two for loops)

**时间复杂度：** **O(n2)** (两个for循环)

### 以上算法的C ++实现 **(**C++ implementation of above algorithm**)** ###

#include<bits/stdc++.h>
    using namespace std;
    
    void findelements(int* a, int n,int K){
        
    	//sort the array using default sort library function, O(logn) generally
    	sort(a,a+n);   
    	//run the first loop
    	for(int k=0;k<n;k++){
        
    		//i=k+1 & j=n-1 (initialized) ; run till i<j
    		for(int i=k+1,j=n-1;i<j;){
          
    			if(a[i]+a[j]+a[k]==K){
          //if sum ==K
    				//print & return
    				printf("three elements are found to sum to %d. These are %d,%d,%d\n",K,a[k],a[i],a[j]); 
    				return;
    			}
    			// if sum <K increment i since array is sorted & we need higher value elements
    			else if (a[i]+a[j]+a[k]<K)  
    				i=i+1;
    			else
    				j=j-1; //  if sum >K decrement j since array is sorted & we need lower value elements
    		}
    	}
    	
    	cout<<"no such three elements can be found"<<endl; // no such element trio found
    	return;
    }
    
    int main(){
        
    	int K,count=0,n;
    	// enter array length
    	cout<<"enter no of elements\n";
    	cin>>n;
    	int* a=(int*)(malloc(sizeof(int)*n));
    	cout<<"enter elements................\n";  //fill the array
    	for(int i=0;i<n;i++)
    	scanf("%d",&a[i]);
    	cout<<"enter the sum,K"<<endl;
    	cin>>K;
    	findelements(a,n,K);           
    
    	return 0;
    }

**Output (first run)**

**输出(首次运行)**

enter no of elements 
    7
    enter elements................ 
    -1 
    5
    6
    9
    23 
    28 
    12 
    enter the sum,K
    28 
    three elements are found to sum to 28. These are -1,6,23

**Output (second run)**

**输出(第二次运行)**

enter no of elements 
    4
    enter elements................ 
    5
    6
    -5 
    7
    enter the sum,K
    1
    no such three elements can be found

> 翻译自: [https://www.includehelp.com/algorithms/find-three-elements-in-an-array-such-that-their-sum-is-equal-to-given-element-k.aspx][https_www.includehelp.com_algorithms_find-three-elements-in-an-array-such-that-their-sum-is-equal-to-given-element-k.aspx]

求出数组中元素的总和

[https_www.includehelp.com_algorithms_find-three-elements-in-an-array-such-that-their-sum-is-equal-to-given-element-k.aspx]: https://www.includehelp.com/algorithms/find-three-elements-in-an-array-such-that-their-sum-is-equal-to-given-element-k.aspx