求出数组中元素的总和_在数组中找到三个元素,使其总和等于给定元素K
程序员文章站
2024-03-15 22:26:51
...
求出数组中元素的总和
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
求出数组中元素的总和