changed 2 years ago  
Published Linked with GitHub

Leetcode刷題學習筆記 – Prefix Sum

Intrudoction

把前面的數字都加起來稱為prefix sum。可以用來解區段和的問題。
prefix sum

prefix sum for 1D Array

最簡單的應用就是用\(O(1)\)算出某個subarray的和。

vector<int> nums;
// 使用STL來計算prefix sum
partial_sum(begin(nums), end(nums), begin(nums));
// 或是使用for loop
for(int i = 1; i < nums.size(); ++i)
    nums[i] += nums[i - 1];

計算出prefix sum之後，就可以用start和end來求subarray sum。

// 求出 index = 2 ~ 5之間的subarray sum
cout << nums[5] - nums[1] << endl;

使用unordered_map/set來記錄走訪過的prefix sum

通常題目會要求符合某個條件的subarray sum。例如:求出subarray sum = K 的subarray個數。

使用unordered_set/map來記錄prefix sum的大小和個數，就可以用\(O(1)\)來查詢之前的pfx數值。 參考 560. Subarray Sum Equals K(Medium)

因為會往前尋找prefix sum，所以必須把0提前加入map或是set中。
因為0的意思是從第0個到目前的subarray sum。

unordered_map<int, int> m{{0, 1}};
unordered_set<int> s{{0}};

Downside and time complexity

Time Complexity Note
initial \(O(N)\) 必須走訪全部的element來建立prefix sum array
getSum \(O(1)\) 只需要計算pfs[end] - pfs[start - 1]
update \(O(N)\) 如果一個數值變了必須update之後所有的pfs

如果使用 BIT(Binary index tree) 就可以達到getSum和update都是\(O(logN)\)

prefix sum for 2D Array

求出綠色/藍色或是紅色框出來的sum。

pfs_2d

計算2D prefix array，其中pfs[y][x]為起點是(0, 0)到(y, x)的sum。

vector<vector<int>> nums;
int m = nums.size();
int n = nums[0].size();
// 為了配合計算方便，使用大一點的vector
vector<vector<int>> pfs(m + 1, vector<int>(n + 1));
for(int y = 1; y <= m; ++y) {
    for(int x = 1; x <= n; ++x) {
        pfs[y][x] = pfs[y - 1][x] + pfs[y][x - 1] + matrix[y - 1][x - 1] - pfs[y - 1][x - 1];
    }
}

計算某個範圍內的sum

int sumRegion(int row1, int col1, int row2, int col2) {
    return pfs[row2 + 1][col2 + 1] - 
           pfs[row2 + 1][col1] - 
           pfs[row1][col2 + 1] +
           pfs[row1][col1];
}

另一種prefix sum for 2D vector

  1. 先針對row做prefix sum
vector<vector<int>> nums;
for(auto& row : nums)
    partial_sum(begin(row), end(row), begin(row));
  1. 定義left和right
    因為2D的range sum是由(top, left) -> (bottom, right)似的值所組成，所以先決定left和right
int m = nums.size();
int n = nums[0].siez();
for(int left = 0; left < n; ++left) {
    for(int right = left; right < n; ++right) {
        
    }
}
  1. 計算每個row從left到right的range sum
    下面是計算(y, left) -> (y, right)
nums[y][right] - (left - 1 >= 0 ? nums[y][left - 1] : 0);
  1. 計算縱向的perfix sum
int pfs = 0;
for(int y = 0; y < m; ++y) {
    pfs += nums[y][right] - 
        (left - 1 >= 0 ? nums[y][left - 1] : 0);
}
  1. 根據題目需求使用unordered_set/map或是set/map。
    參考

560. Subarray Sum Equals K(Medium)

給你一個vector<int> nums，求出subarray的和是k的個數。

  1. 一開始我是使用dp的方法，dp[i][j]，其中i代表開始，j代表結束，dp[i][j] = dp[i][j - 1] + nums[j]。但是這個方法會timeout。因為為O(N^2)。
  2. 使用prefix sum，解法如下，也是會timeout。因為還是O(N^2)的演算法。















int subarraySum(vector<int>& nums, int k) {
    int n = nums.size(), rtn{0};
    vector<int> sum(n + 1, 0);
    sum[1] = nums[0];
    for(int i = 2; i <= n; ++i)
        sum[i] = nums[i - 1] + sum[i - 1];
        
        
    for(int i = 1; i <= n; ++i) {
        for(int j = i; j <= n; ++j) {
            if(sum[j] - sum[i - 1] == k) rtn++;
        }
    }
    return rtn;
}
  1. 如下圖，當index走到i的時候，把這邊當終點，往前回推n個如果和是k，那這個subarray就是一個解。n前面的和即為sum - k。用一個hashmap紀錄prefix sum的個數，就可以達到O(N)。












int subarraySum(vector<int>& nums, int k) {
    int n = nums.size(), rtn{0}, sum{0};
    unordered_map<int, int> m{{0, 1}}; //self
    for(auto& n : nums) {
        sum += n;
        rtn += m[sum - k];
        m[sum]++;
    }
        
    return rtn;
}

對sorted array做prefix sum

1508. Range Sum of Sorted Subarray Sums

  1. 題目是對sorted array做prefix sum，然後要找出排序後從left到right的總和。
  2. 因為是sorted array所以出現的subarray sum從小到大的順序可以預測。
// 這題的題目是對"sorted array" 做處理。 因為是sorted array[1, 2, 3, 4]
// 從1開始的subarray : [1], [1, 2], [1, 2, 3], [1, 2, 3, 4] ==> subarray sum = [1, 3, 6, 10]
// 從2開始的subarrry : [2], [2, 3], [2, 3, 4] ==> subarray sum = [2, 5, 9]
// 從3開始的subarray : [3], [3, 4] ==> subarray sum = [3, 7]
// 從4開始的subarray : [4] ==> subarray sum = [4]
int rangeSum(vector<int>& nums, int n, int left, int right) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(int i = 0; i < n; ++i)
        pq.push({nums[i], i + 1}); // 每一個數字開頭的subarray，長度只有1
        
    int ans = 0, m = 1e9 + 7;
    for(int i = 1; i <= right; ++i) {
        auto p = pq.top(); pq.pop();    // 先取出最小的
        if(i >= left)
            ans = (ans + p.first) % m;
        if(p.second < n) {  // 加上下一個數字，例如 : [2, 3] --> [2, 3, 4], 長度 + 1
            p.first += nums[p.second++];
            pq.push(p);
        }
    }
        
    return ans;
}

將Array轉換為正負值，求prefix sum。

有的題目必須將array轉換為正負值，這樣比較方便比較兩種不同性質的element。

  • 通常是求subarray或是interval的題目。也就是連續數值。
  • 可以將數值分成兩種特性(+1/-1)

1124. Longest Well-Performing Interval

題目是說數值大於8的為tiring day, well-performing interval定義為某個interval中tiring day的日子大於non-tiring day的日子。

  1. 將大於8的數值定義為1, 小於等於8的數值為-1。
  2. 使用prefix sum
  3. 一開始我是使用以下的code，從最開始找，直到sum - 1。




map<int, int> m;
for(auto it = m.begin(); it->first <= sum - 1; ++it) {
    ans = max(ans, i - it->second);                                        
}
  1. 因為我們只儲存第一個出現的index，越接近0的數值越早出現。所以我們只要檢查sum - 1即可。參考這邊的解說。
























int longestWPI(vector<int>& hours) {       
    int ans = 0, sum = 0;
    unordered_map<int, int> m;//value, index
    m[0] = -1;
    for(int i = 0; i < hours.size(); ++i) {
        sum += hours[i] > 8 ? 1 : -1;
        if(sum > 0) ans = max(ans, i + 1); // 因為大於0就是全部的長度是最長的
        else {
            if(m.count(sum - 1)) ans = max(ans, i - m[sum - 1]);
            if(!m.count(sum)) m[sum] = i;
        }
    }
    return ans;
}
//      這種問題都是從0開始
//      6, 6, 6, 9, 6, 9, 9
//  0|x
// -1|  x                 x
// -2|     x     x     x
// -3|        x     x
// 最後一個9, sum = -1, 可以找到符合的有-2, -3
// 因為我們都只存最前面的-2，而且要到-3，必須先經過-2，
// 所以-2永遠會比-3還前面，所以不用檢查小於-2的數值。
// 也就是我們只儲存第一個數值，所以越接近0的數值一定越早出現。

525. Contiguous Array

給你一個binary array，找出1和0數目一樣的最長subarray。




















class Solution {
    //[ 0,  0,  1,  1,  1,  0]
    //[-1, -2, -1,  0,  1,  0]
    //     ------
public:
    int findMaxLength(vector<int>& nums) {
       unordered_map<int, int> m; // value, index
       m[0] = -1; // 因為也是prefix sum的概念，所以必須加上開頭
       int balance{0}, ans{0};
       for(int i = 0; i < nums.size(); ++i) {
           balance += nums[i] ? 1 : -1;
           if(m.count(balance)) ans = max(ans, i - m[balance]);
           else m[balance] = i;
       }
       // time  : O(N)
       // space : O(N)
       return ans;
    }
};

Problems

1658. Minimum Operations to Reduce X to Zero

一開始看到了minimum operrations，就使用了DP結果TLE。看了hints，因為只能從最左和最右刪除，所以最後只會剩下subarray，所以問題就可變成找出最長的subarray，則sz - subarray.size() 就會是minimal operations。

下面的解法是用prefix sum + hash table。
time complexity : \(O(N)\)
space complexity : \(O(N)\)


















int minOperations(vector<int>& nums, int x) {
    int sz = nums.size();
    int total = accumulate(nums.begin(), nums.end(), 0);
    if(x > total) return -1;
    if(x == total) return sz;
    int target = total - x;
    unordered_map<int, int> m;
    m[0] = -1;
    int sum = 0, maxlen = 0;
    for(int i = 0; i < sz; ++i) {
        sum += nums[i];
        if(sum >= target && m.count(sum - target))
                maxlen = max(maxlen, i - m[sum - target]);
        m[sum] = i;
    }
    return maxlen > 0 ? sz - maxlen : -1;
}

1074. Number of Submatrices That Sum to Target

給你一個2D Array求出，subarray的和為target的個數。

  1. 一開始使用 2D array算prefix的做法，但是time complexity非常差。



















int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
    int m = matrix.size();
    int n = matrix[0].size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    int rtn = 0;
    for(int y = 0; y < m; ++y) {    // bottom
        for(int x = 0; x < n; ++x) { // right
            dp[y + 1][x + 1] = dp[y][x + 1] + dp[y + 1][x] - dp[y][x] + matrix[y][x];
            for(int i = 0; i <= y; ++i) {   // top
                for(int j = 0; j <= x; ++j) { //left
                    if(dp[y + 1][x + 1] - dp[i][x + 1] - dp[y + 1][j] + dp[i][j] == target) rtn++;
                }
            }
        }
    }
    // time  : O(MN * MN)
    // space : O((MN))
    return rtn;
}
  1. 這題是560. Subarray Sum Equals K(Medium)變成2D版本。
  2. 所以問題可以變成怎麼把2D版本變成1D版本。
  3. 先對row做prefix sum
  4. 再掃描left和right找出，符合條件的個數。























int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
    int m = matrix.size();
    int n = matrix[0].size();
    for(int i = 0; i < m; ++i)
        partial_sum(matrix[i].begin(), matrix[i].end(), matrix[i].begin()); // O(MN)
        
    unordered_map<int, int> counter; // prefix sum, count
    int ans = 0;
    for(int left = 0; left < n; ++left) {
        for(int right = left; right < n; ++right) {
            counter = {{0, 1}}; // clear map and add only one item
            int pfs = 0;
            for(int k = 0; k < m; ++k) {
                pfs += matrix[k][right] - (left - 1 >= 0 ? matrix[k][left - 1] : 0);
                ans += counter[pfs - target];
                counter[pfs]++;
            }
        }    
    }
    // time  : O(MN + MNM) = O(MNM)
    // psace : O(MN)
    return ans;
}

363. Max Sum of Rectangle No Larger Than K

int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
    for(auto& row : matrix)
        partial_sum(begin(row), end(row), begin(row));
        
    int m = matrix.size();
    int n = matrix[0].size();
    int ans = INT_MIN;
    for(int left = 0; left < n; ++left) {
        for(int right = left; right < n; ++right) {
            int pfs = 0;
            set<int> s{0};
            for(int y = 0; y < m; ++y) {
                pfs += matrix[y][right] - (left - 1 >= 0 ? matrix[y][left - 1] : 0);
                auto it = s.lower_bound(pfs - k);
                if(it != s.end()) ans = max(ans, pfs - *it);
                s.insert(pfs);
            }
        }
    }
    return ans;        
}

523. Continuous Subarray Sum

給你一個vector<int>和k，找出subarray sum為k的倍數。且長度至少為2。

  1. 一開到subarray sum就想到使用prefix sum
  2. 如果只是求剛好等於k的話，那就是查詢遇到的prefix sum始有否k - cur_pfs。
  3. 但是這邊是要k的倍數。k的倍數意味著，0, k, 2k, 3k, …

假設從第i個到第j個的subarry sum為k的倍數。
pfs(j) - pfs(i - 1) = m * k
兩邊各取mod k，則 pfs(j) % k - pfs(i - 1) % k = 0
=> pfs(j) % k = pfs(i - 1) % k

把prefix sum用mod K存起來，只要遇到和目前prefix sum mod k 相同的值，即為我們要的。

  1. 因為長度最少要2以上，所以對相同的prefix sum來說，我們只需要儲存index最小的那一個，因為這樣可以保證長度是最長的。
bool checkSubarraySum(vector<int>& nums, int k) {
    if(k == 1) return nums.size() >= 2;
    // 因為只要知道最小index的prefix sum(4)
    unordered_map<int, int> m{{0, -1}}; // prefix sum, minamum idx
    int pfs{0};
    for(int i = 0; i < nums.size(); ++i) {
        pfs = (pfs + nums[i]) % k;
        if(m.count(pfs) && i - m[pfs] >= 2) return true;
        if(!m.count(pfs)) m[pfs] = i;
    }
    return false;
}

974. Subarray Sums Divisible by K

給你一個vector<int>和K，找出subarray的個數使得subarray sum為可以被K整除。這邊數值會有負數。

  1. 因為subarray sum所以使用prefix sum
  2. 統計prefix sum出現的個數，就可以計算符合條件的subarray個數。
  3. 因為要可以整除K，所以觀念和523. Continuous Subarray Sum一樣。

pfs(cur) - pfs(prev) = m * K
pfs(cur) % K = pfs(prev) % K

  1. 可是這邊有負數!! 參考負數mod

因為 -1 % 3 = -2
所以使用 (n%k + k) % k，因為n為正整數結果不變。
如果是負數，則 -1 % 3 = -1。 (-1 + 3) % 3 = 2。
(1 + (-1) % 3 + 3) % 3 = 0，才是我們要的結果。

int subarraysDivByK(vector<int>& nums, int k) {
    unordered_map<int, int> m{{0, 1}}; //prefix sum % k, count
    int pfs{0}, ans{0};
    for(auto& n : nums) {
        pfs = (pfs + n % k + k) % k;
        // pfs(cur) - pfs(prev) = m * k
        // pfs(cur) % k = pfs(prev) % k
        // 因為n 有可能為negative, 所以必須用 n % k + k
        ans += m[pfs];
        m[pfs]++;
    }
    return ans;
}

862. Shortest Subarray with Sum at Least K

給你一個vector<int>和K，求出subarray sum最少為K，返回最短的長度，如果沒有則返回-1。

  1. 看到subarray sum那就是使用 prefix sum
  2. 因為是最短的長度，所以和523. Continuous Subarray Sum相反，當prefix sum一樣的時候，只要存最大index就可以。這樣長度才會最短。
  3. 另外使用long避免prefix sum加到overflow。
  4. 因為是subarray sum最少為k，

pfs(cur) - pfs(prev) >= k, i < j
pfs(prev) <= pfs(cur) - k
必須嘗試所有比pfs(cur) - k還小的值。

  1. 所以使用upper_bound找出 > pfs(cur) - k的值，然後從前一個開始嘗試。
  2. 最後把現在的pfs插入到map中，因為插入的index一定是最大值，所以把比目前的pfs還大的都刪除掉。
  3. 因為保留了最大index的pfs所以(5)不用全部都試，只需要試前upper_bound的前一個即可。
int shortestSubarray(vector<int>& nums, int k) {
    int sz = nums.size();
    map<long, int> m{{0, -1}}; //prefix sum, maximum index
    int minans = sz + 1;
    long pfs{0};
    for(int i = 0; i < nums.size(); ++i) {
        pfs += nums[i];
        auto it = m.upper_bound(pfs - k);
        if(it != m.begin()) {
            it = prev(it, 1);
            minans = min(minans, i - it->second);
        }
        m[pfs] = i;
        while(m.rbegin()->first != pfs)
            m.erase(m.rbegin()->first);
    }
    return minans == sz + 1 ? -1 : minans;
}
tags: leetcode 刷題
Select a repo