subarray类型题目

使用prefixSum 让subarray的操作简易
402. Continuous Subarray Sum

和41. Maximum Subarray

基本一样

class Solution {
public:
    /*
     * @param A: An integer array
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    vector<int> continuousSubarraySum(vector<int> &A) {
        // write your code here
        //这个题和max subarray sum有啥区别
        const int size = A.size();
        vector<int> res; 
        if(size == 0){
            return res; 
        }
        int prefixSum = 0; 
        int minSum = 0, minIdx = -1;
        int maxV = INT_MIN; 
        res = vector<int>(2, 0); 
        for(int i = 0; i < size; i++){
            prefixSum += A[i]; 
            if(maxV < prefixSum - minSum){
                maxV = prefixSum - minSum;
                res[0] = minIdx + 1;
                res[1] = i; 
            }
            if(prefixSum < minSum){
                minSum = prefixSum;
                minIdx = i; 
            }
        }
        return res; 
    }
};

1457. Search Subarray (使用hash 建立prefixSum和index之间关系)
int searchSubarray(vector<int> &arr, int k) { // Write your code here const int size = arr.size(); if(size == 0){ return -1; } unordered_map<int, int> toPos; toPos[0] = -1; int sum = 0; for(int i = 0; i < size; i++){ sum += arr[i]; if(toPos.find(sum - k) != toPos.end()){ return i - toPos[sum - k]; } if(toPos.find(sum) == toPos.end()){ toPos[sum] = i; } } return -1; }

Code(Language:C++)