SubarraySum（子数组总和）

蔚落 2024-03-23 15:00 48阅读 0赞

## 问题 ##

给定一个整数数组，求该数组所有子数组中所有元素的和。

例如，一个包含三个元素的数组\[4,5,6\]可以分成以下子数组:  
1个元素数组：\[4\],\[5\],\[6\]  
2个元素数组：\[4,5\],\[5,6\],\[4,6\]  
3个元素数组：\[4,5,6\]

所有子数组中所有元素的和为：4 + 5 + 6 +(4+5)+(5+6)+(4+5+6)=50

## 解决思路 ##

通过**按位对应法**来解决这个问题。  
所有元素，在每个子数组中只有**存在**与**不存在**两种状态。  
逐位遍历进行所有子集

## 源码 ##

通过递归获取所有子数组，然后进行计算各数组所有元素总和

public int sum(int [] nums){
        
        boolean isInArray[] = new boolean[nums.length];
        List<List<Integer>> subArrays = new ArrayList<List<Integer>>();
        findSubArray(nums,0,isInArray,subArrays);
        int sum = 0;
        for(int i = 0;i<subArrays.size();i++){
        
            List<Integer> subArray = subArrays.get(i);
            System.out.println(subArray.toString());
            for(int j=0;j<subArray.size();j++){
        
                sum+=subArray.get(j);
            }
        }
        return sum;
    
    
    }
    
    public void findSubArray(int arr[],int index,boolean isInArray[],List<List<Integer>> subArrays){
        
        int length  = arr.length;
        if(index==length){
        
            List<Integer> subArray = new ArrayList<Integer>();
            for(int i = 0;i<length;i++){
        
                if(isInArray[i]){
        
                    subArray.add(arr[i]);
                }
            }
            if(subArray.size()>0){
        
                subArrays.add(subArray);
            }
        }else{
        
            isInArray[index] = true;
            findSubArray(arr,index+1,isInArray,subArrays);
            isInArray[index] = false;
            findSubArray(arr,index+1,isInArray,subArrays);
        }
    }