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
Return 1.

二. 題目分析

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

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

三. 示例代碼

#include 
#include 

using namespace std;

class Solution {
public:
    int minPatches(vector& 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;
    }
};

四. 小結

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