1513. 最多只包含一個 1 的子字串

思路

題目要找到所有子字串為 1 的數量。

首先，紀錄 0 出現的位置，用next數組存，next[i + 1]（記得 + 1）代表位置 i 之後看到第一個 0 的位置。

指針i遍歷數字 1，next[i + 1]表示自己遇到第一個1的位置，
滿足條件的子字串，在固定左邊的情況下，一共有next[i + 1] - i個。
將所有數字相加即為所求。

由於每次只會用到一個位置，能省去next的空間，轉為一個變數zeroPos存位置，
倒序遍歷，將原先兩個迴圈合併。

程式碼

1. 遍歷

class Solution {
public:
    int numSub(string s) {
        const int MOD = 1e9 + 7;
        int n = s.size();
        int next[n + 1]; // next[i + 1] 代表位置 i 之後看到第一個 0 的位置
        next[n] = n;
        for(int i = n - 1; i >= 0; --i) {
            next[i] = next[i + 1];
            if(s[i] == '0') {
                next[i] = i;
            }
        }
        int res = 0;
        for(int i = 0; i < n; ++i) { // 固定左邊
            // 找到右邊的位置
            if(s[i] == '1') {
                res += next[i + 1] - i;
                res %= MOD;
            }
       }
        return res;
    }
};

2. 節省空間，一次遍歷

class Solution {
public:
    int numSub(string s) {
        const int MOD = 1e9 + 7;
        int n = s.size();
        int res = 0;
        int zeroPos = n;
        for(int i = n - 1; i >= 0; --i) {
            if(s[i] == '0') {
                zeroPos = i;
            }
            else {
                res += zeroPos - i;
                res %= MOD;
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：方法一$O(n)$，方法二$O(1)$