在给定的数组中查找一个数_查找给定总和的子数组

太过爱你忘了你带给我的痛 2023-03-05 12:42 18阅读 0赞

在给定的数组中查找一个数

**Problem Statement:** Given an unsorted array **A** of size **N** of non-negative integers, **find a continuous sub-array which adds to the given number**.

**问题陈述：**给定一个大小为**N**的非负整数的未排序数组**A** ，请**找到一个连续的子数组，该子数组加到给定的number上** 。

**Solution**

**解**

**Algorithm:**

**算法：**

1.  A in the input array, n is the length of the array & s in the given sum.
    
    A中的输入数组中，n是在给定的总和的阵列＆S的长度。
2.  Initialize vector b. (for storing indexes of subarray)
    
    初始化向量b 。 (用于存储子数组的索引)
3.  Initialize a variable cur\_sum=0
    
    初始化变量cur\_sum = 0
4.  for i=0:n-1
    
    对于i = 0：n-1
5.      set cur_sum=A[i]
        	for j=i+1:n-1
        		add A[j] to cur_sum
        		if(cur_sum==s)
        			i is the starting index of subarray found
        			j is the end index of subarray found
        			print elements between indexes i & j
                    (including i & j) & return to main
        		end if
        		if cur_sum become greater than s then break loop
        	end for
        end for
6.  If control comes out of the loop that means so such subarray exists, thus print **"no subarray found"**.
    
    如果控制退出循环，这意味着该子数组存在，因此打印**“未找到子数组”** 。

## C ++实现查找具有给定总和的子数组 **(**C++ implementation to find subarray with given sum**)** ##

#include <bits/stdc++.h>
    using namespace std;
    
    vector<int> find(vector<int> a,int n,int s){
        
    	vector<int> b; //output vector
    	int cur_sum=0;
    	for(int i=0;i<n;i++){
        
    		cur_sum=a[i];//cur_suming element
    		for(int j=i+1;j<n;j++){
        
    			//add next element contigeously 
    			cur_sum=cur_sum+a[j]; 
    			// if current sum  is eaqual to the sum value
    			if(cur_sum==s){
         
    				//insert array index of the cur_sum element in sub array
    				b.push_back(i); 
    				//insert array index of the last element in sub array
    				b.push_back(j); 
    				return b;
    			}
    			if(cur_sum>s)
    				break;
    		}
    	}
    	// if no such sub array exists
    	b.push_back(-1); 
    	return b;
    } 
    
    int main() {
        
    	//code
    	int s,n,no;
    	cout<<"enter array length & Sum respectively"<<endl;
    	scanf("%d%d",&n,&s);
    
    	vector<int> a; //input array
    
    	cout<<"enter array elements........"<<endl;
    	for(int j=0;j<n;j++){
        
    		scanf("%d",&no);
    		a.push_back(no); //inserting array elements
    	}
    
    	vector<int> b=find(a,n,s);
    	if(b[0]==-1)
    		printf("subarray not found");
    	else{
        
    		cout<<"Subarray is: ";
    		for(int i=b[0];i<=b[1];i++)
    			cout<<a[i]<<" ";
    		cout<<endl;
    	}	    
    	return 0;
    }

**Output**

**输出量**

First run:
    enter array length & Sum respectively
    8
    20 
    enter array elements........ 
    4
    2
    10 
    3
    -3 
    10 
    5
    5
    Subarray is: 10 3 -3 10 
    
    
    Second run:
    enter array length & Sum respectively
    6
    15 
    enter array elements........ 
    5
    1
    -6 
    7
    7
    3
    subarray not found

> 翻译自: [https://www.includehelp.com/icp/finding-subarray-with-given-sum.aspx][https_www.includehelp.com_icp_finding-subarray-with-given-sum.aspx]

在给定的数组中查找一个数

[https_www.includehelp.com_icp_finding-subarray-with-given-sum.aspx]: https://www.includehelp.com/icp/finding-subarray-with-given-sum.aspx