資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究查詢是否可以用 C++ 將一個數組分成兩個等於和的子陣列
假設我們有一個數組 A。我們必須檢查是否可以將陣列分成兩部分，其和相等。假設元素是 [6, 1, 3, 2, 5]，則 [6, 1] 和 [2, 5] 可能是兩個子陣列。
可以遵循以下規則輕鬆解決此問題。我們必須首先找到陣列中所有元素的總和，然後對於陣列的每個元素，我們可以使用 total_sum 減去目前找到的元素之和來計算右和。
示例
#include<iostream>
#include<numeric>
using namespace std;
void displaySubArray(int arr[], int left, int right) {
cout << "[ ";
for (int i = left; i <= right; i++)
cout << arr[i] << " ";
cout << "] ";
}
void subarrayOfSameSum(int arr[] , int n) {
int total_sum = accumulate(arr, arr+n, 0);
int so_far_sum = 0;
for(int i = 0; i<n; i++){
if(2*so_far_sum+arr[i] == total_sum){
cout << "subarray 1: "; displaySubArray(arr, 0, i-1);
cout << "\nsubarray 2: "; displaySubArray(arr, i+1, n-1);
return;
}
so_far_sum += arr[i];
}
cout << "No subarray can be formed";
}
int main() {
int arr[] = {6, 1, 3, 2, 5} ;
int n = sizeof(arr)/sizeof(arr[0]);
subarrayOfSameSum(arr, n);
}輸出
subarray 1: [ 6 1 ] subarray 2: [ 2 5 ]
更新於： 01-11-2019
138 次瀏覽
廣告