Portfolio


Input: nums = [1,3,0,0,2,0,0,4]
Output: 6
Explanation:
There are 4 occurrences of [0] as a subarray.
There are 2 occurrences of [0,0] as a subarray.
There is no occurrence of a subarray with a size more than 2 filled with 0. Therefore, we return 6.


Input: nums = [0,0,0,2,0,0]
Output: 9
Explanation:
There are 5 occurrences of [0] as a subarray.
There are 3 occurrences of [0,0] as a subarray.
There is 1 occurrence of [0,0,0] as a subarray.
There is no occurrence of a subarray with a size more than 3 filled with 0. Therefore, we return 9.


Input: nums = [2,10,2019]
Output: 0
Explanation: There is no subarray filled with 0. Therefore, we return 0.


const zeroFilledSubarray = function(nums) {
    const arr = Array.from({length: 100001}, () => 0);
    const zeros = [];
    let answer = 0;
    let isContinuous = false;
    let count = 0;

    arr[1] = 1;

    for(let i = 1; i < 100001; i++) {
        arr[i] = arr[i - 1] + i;
    }

    for(let i = 0; i < nums.length; i++) {
        if(nums[i] === 0) {
            count++;

            if(!isContinuous) {
                isContinuous = true;
            }
        } else {
            if(isContinuous) {
                zeros.push(count);
            }
            count = 0;
            isContinuous = false;
        }
    }

    if(isContinuous) {
        zeros.push(count);
    }

    for(let i = 0; i < zeros.length; i++) {
        answer += arr[zeros[i]];
    }

    return answer;
};


/**
 * @param {number[]} nums
 * @return {number}
 */
var zeroFilledSubarray = function (nums) {
    const cache = {};
    let curZeroCnt = 0;
    let answer = 0;

    const addToAnswer = () => {
        if (cache[curZeroCnt]) {
            answer += cache[curZeroCnt];
        }
        else {
            const cnt = getZeroCnt(curZeroCnt);
            answer += cnt;
            cache[curZeroCnt] = cnt;
        }
        curZeroCnt = 0;
    }

    nums.forEach(num => {
        if (num === 0) {
            curZeroCnt += 1;
        }
        if (curZeroCnt !== 0 && num !== 0) {
            addToAnswer();
        }
    });

    if (curZeroCnt !== 0) {
        addToAnswer();
    }

    return answer;
};

function getZeroCnt(num) {
    let res = 0;
    for (let i = 1; i <= num; i++) {
        res += i;
    }
    return res;
}


/**
 * @param {number[]} nums
 * @return {number}
 */
const zeroFilledSubarray = (nums) => {
  let cnt = 0;
  let total = 0;

  for (let i = 0; i < nums.length; i += 1) {
    const now = nums[i];

    if (now === 0) {
      cnt += 1;
      total += cnt;
    } else {
      cnt = 0;
    }
  }

  return total;
};

Number of Zero-Filled Subarray

문제

풀이