讨论/《高频算法实战》 - 求数组区间和/
《高频算法实战》 - 求数组区间和
共 2 个回复

import java.util.*;
class Solution{
public int[] array_interval_sum(int[] nums, int[][] queries) {
int n = nums.length;
int m = queries.length;
int[] ans = new int[m];
ArrayList arr1 = new ArrayList();
ArrayList prefix = new ArrayList();
prefix.add(0);
int sum = 0;
for(int i = 1;i<=n;i++){//生成前缀和数组
sum+=nums[i-1];
prefix.add(i,sum);//[0,1,3,5,7,8];
}

    for(int j = 0;j<queries.length;j++){
        int left = queries[j][0];
        int right = queries[j][1];
        int num1=(int)prefix.get(right),num2=(int)prefix.get(left-1);
        sum =num1-num2;
        arr1.add(sum);
    }

    //Arraylist转换成int[]
    for(int k = 0;k < arr1.size();k++){
        ans[k] = (int)arr1.get(k);
    }

    return ans;
}

}

C++

class Solution {
public:
    vector<int> array_interval_sum(vector<int>& nums, vector<vector<int>>& queries) {
        int q = queries.size();
        int sum;
        vector<int> vec;
        for(int i = 0;i<q;i++)
        {
            sum = 0;
            for(int j = queries[i][0]-1;j<queries[i][1];j++)
                sum += nums[j];
            vec.emplace_back(sum);
        }
        return vec;
    }
};

image.png