leetcode筆記：Patching Array

一. 題目描述

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range[1, n]inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:
nums = [1, 3], n = 6
Return1.

二. 題目分析

題目的大意是，給定一個數組nums和一個數n，求添加最少的數使得區間[1, n]中的每個數都可以由數組nums中元素累加組成。

由于數組已經排序，因此基本的思路是，定義一個整形變量currSum，假設數組nums目前可以累加的數的范圍為[1, currSum)，如果此時向數組中添加一個元素k（k <= currSum）可以將累加的數的范圍擴充為[1, currSum + k)，而題目中要求向數組nums添加元素的次數最少，因此當且僅當k = currSum時，累加數的范圍可以取到上限[1, 2 * currSum)。在遍歷數組nums時，有以下兩種操作：

1. 當數組中有小于等于currSum的元素nums[index]時，則利用數組中的元素，同時currSum += nums[index]；
2. 若沒有，則添加新元素currSum入數組，此時范圍擴展至最大，同時令currSum <<= 1。

三. 示例代碼

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        int result = 0, index = 0;
        // currSum標記了當前數組nums可累加到的最大范圍[1, currSum)
        for (int currSum = 1; currSum <= n; )
        {
            // 數組內元素小于currSum時，可累加的sum上限增加為
            // currSum + nums[index]，然后數組索引值加1
            if (index < nums.size() && nums[index] <= currSum)
                currSum += nums[index++];
            else
            {   
                currSum <<= 1; // 添入元素后，可累加的sum范圍加倍
                ++result;
            }
        }
        return result;
    }
};

四. 小結

這種方法并不容易馬上想到，對于這一類型的問題，特別需要在紙面上多列舉例子，慢慢從中找出規律。