数组中求连续连续个数和最小的数

你的名字 2021-11-16 16:10 341阅读 0赞

题目描述：求数组中连续个数之和最小的数。要求数组长度n>1。 例如：在5 10 15 -20 -10 20的序列中，连续数之和最小的数就是 -20和-10。

算法思想：利用双层循环依次遍历数组中的数，外层循环表示本次遍历开始的位置，内层循环用来计算从外层循环开始的位置依次相加后面的数用sum变量存储，每次相加之后与最小值min比较，若小于最小值则把开始时的数组下标和当前所加到的数组下标记录下来(这里用pre和last变量存储)，并修改min的值，直到双层循环结束。 算法时间复杂度O(n2)。  
算法代码：

void min_arr(int arr[], int n, int &pre, int &last){
    	int sum,min;
    	min = arr[0] + arr[1];
    	for (int i = 0; i < n; i++){
    		sum = arr[i];
    		for (int j = i + 1; j < n; j++){
    			if (sum + arr[j] < min){
    				pre = i;
    				last = j;
    				min = sum + arr[j];
    			}
    			sum = sum + arr[j];
    		}
    	}
    
    }

完整代码：

#include<stdlib.h>
    #include<stdio.h>
    #include<iostream>
    using namespace std;
    void min_arr(int arr[], int n, int &pre, int &last){
    	int sum,min;
    	min = arr[0] + arr[1];
    	for (int i = 0; i < n; i++){
    		sum = arr[i];
    		for (int j = i + 1; j < n; j++){
    			if (sum + arr[j] < min){
    				pre = i;
    				last = j;
    				min = sum + arr[j];
    			}
    			sum = sum + arr[j];
    		}
    	}
    
    }
    int main(){
    	int n,pre=0,last=0;
    	cout << "输入数组的长度：";
    	cin >> n;
    	int *arr = (int*)malloc(sizeof(int)*n);
    	cout <<"\n"<<"输入数组的值：";
    	for (int i = 0; i < n; i++){
    		cin >> arr[i];
    	}
    	min_arr(arr, n,  pre, last);
    	cout << "\n" << "数组中连续个数之和最小的数为：";
    	for (int i = pre; i <= last; i++){
    		cout << arr[i] << "\t";
    	}
    	system("pause");
    	return 0;
    }

运行结果：

![20190729002540447.png][]

若有更好的方法，欢迎留言指导。

[20190729002540447.png]: /images/20211116/af1424f9cb6d46f69cb5d2151472fa23.png