两个列表的最小索引总和_在最小时间复杂度中找到总和最接近零的对

偏执的太偏执、 2023-03-05 04:29 40阅读 0赞

两个列表的最小索引总和

**Problem statement**

**问题陈述**

Given an array with both positive and negative integers. Find the pair whose sum is closest to zero in minimum time complexity.

给定一个既有正整数又有负整数的数组。 找到总和最接近零的最小时间复杂度对。

**Description:**

**描述：**

Here we are going to see the algorithm with minimum time complexity to find a pair such that their sum is closest to 0.

在这里，我们将看到具有最小时间复杂度的算法，以找到对使得它们的总和最接近0。

**Algorithm:**

**算法：**

1.  Sort the array.
    
    对数组进行排序。
2.  Maintain two indexes, one at beginning, i, (i=0) & the other at the ending, j, (j=n-1, where n is the array length).
    
    保持两个索引，一个索引在开头i (i = 0) ，另一个索引在结尾j ( j = n-1 ，其中n是数组长度)。
3.  Maintain two variables indexP and indexN to keep track of the pairs which sum closest to 0.
    
    保持两个变量indexP和indexN来跟踪总和最接近0的对。
4.  Set a variable minsum to INT\_MAX.
    
    将变量minsum设置为INT\_MAX 。
5.  While (i<j)
    
    而(i <j)
    
     *  If abs(current pair-sum)< abs(minsum)
     *  If(current pair-sum>0)
6.  End loop
    
    结束循环
7.  indexP & indexN marks to the pair that sum closest to 0.
    
    indexP和indexN标记为总和最接近0的对。
8.  Print array\[indexN\] & array\[indexP\].
    
    打印array \[indexN\]和array \[indexP\] 。

**Time complexity:** O(nlogn) (O(logn) for sorting the array)

**时间复杂度：** O(nlogn)(用于数组排序的O(logn))

**Space complexity:** O(1)

**空间复杂度：** O(1)

## 该算法的C ++实现 **(**C++ implementation of the algorithm **)** ##

#include<bits/stdc++.h>
    using namespace std;
    
    void findpairs(int* a, int n){
        
    	//sort the array using default sort library function, O(logn) generally
    	sort(a,a+n);   
    	int temp,i=0,j=n-1,minsum=INT_MAX,indexN=i,indexP=j;
    
    	while(i<j){
        
    		// current pair-sum
    		temp=a[i]+a[j];  
    		//if abs(current pair-sum)<abs(minsum)
    		if(abs(temp)<abs(minsum)){
              
    			minsum=temp;
    			indexN=i;
    			indexP=j;
    		}
    		//if current pair-sum<0
    		if(temp<0){
          
    			//Increment i
    			i++;           
    		}
    		else		
    		j--; // Decrement j
    	}
    	
    	//print the pair
    	cout<<"the pair is "<<a[indexN]<<","<<a[indexP]<<endl;    
    }
    
    int main(){
        
    
    	int x,count=0,n;
    
    	// enter array length
    	cout<<"enter no of elements\n";        
    	cin>>n;
    	
    	int* a=(int*)(malloc(sizeof(int)*n));
    	
    	//fill the array
    	cout<<"enter elements................\n";  
    	for(int i=0;i<n;i++)
    		scanf("%d",&a[i]);
    
    	findpairs(a,n);           
    
    	return 0;	
    }

**Output**

**输出量**

enter no of elements
    9
    enter elements................
    11
    -4
    7 
    31
    -30
    -6
    8
    17
    -14
    the pair is -30,31

> 翻译自: [https://www.includehelp.com/algorithms/find-the-pair-whose-sum-is-closest-to-zero-in-minimum-time-complexity.aspx][https_www.includehelp.com_algorithms_find-the-pair-whose-sum-is-closest-to-zero-in-minimum-time-complexity.aspx]

两个列表的最小索引总和

[https_www.includehelp.com_algorithms_find-the-pair-whose-sum-is-closest-to-zero-in-minimum-time-complexity.aspx]: https://www.includehelp.com/algorithms/find-the-pair-whose-sum-is-closest-to-zero-in-minimum-time-complexity.aspx