1588. Sum of All Odd Length Subarrays

[twy30]

https://leetcode.com/problems/sum-of-all-odd-length-subarrays/

using System.Linq;

public class Solution
{
    public int SumOddLengthSubarrays(int[] arr)
    {
        // 「輸入的數字」（複數）
        var inputNumbers = arr;

        // This is how we will solve this in O(n) time.
        //
        // Say we have inputNumbers like this:
        //
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        //
        // ---
        //
        // These are all of the 1-length subarrays:
        //
        // {n₁}
        //     {n₂}
        //         {n₃}
        //             {n₄}
        //                 {n₅}
        //                     {n₆}
        //                          ...
        //                               {n₋₆}
        //                                    {n₋₅}
        //                                         {n₋₄}
        //                                              {n₋₃}
        //                                                   {n₋₂}
        //                                                        {n₋₁}
        //
        // They add up like this:
        //
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        //
        // ---
        //
        // These are all of the 3-length subarrays:
        //
        // {n₁, n₂, n₃}
        //     {n₂, n₃, n₄}
        //         {n₃, n₄, n₅}
        //             {n₄, n₅, n₆}
        //                 {n₅, n₆, ...
        //                     {n₆, ...
        //                          ...
        //                          ... , n₋₆}
        //                          ... , n₋₆, n₋₅}
        //                               {n₋₆, n₋₅, n₋₄}
        //                                    {n₋₅, n₋₄, n₋₃}
        //                                         {n₋₄, n₋₃, n₋₂}
        //                                              {n₋₃, n₋₂, n₋₁}
        //
        // They add up like this:
        //
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        // {    n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂,    }
        // {        n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃,         }
        //
        // It is equivlent to:
        //
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        // -n₁                                                    -n₋₁
        // -n₁ -n₂                                           -n₋₂ -n₋₁
        //
        // ---
        //
        // We can list all 5-length subarrays and add them up.  It will
        // turn out like this:
        //
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        // -n₁                                                    -n₋₁
        // -n₁ -n₂                                           -n₋₂ -n₋₁
        // -n₁ -n₂ -n₃                                  -n₋₃ -n₋₂ -n₋₁
        // -n₁ -n₂ -n₃ -n₄                         -n₋₄ -n₋₃ -n₋₂ -n₋₁
        //
        // ---
        //
        // This is the case for 7-length subarrays.
        //
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        // {n₁, n₂, n₃, n₄, n₅, n₆, ... , n₋₆, n₋₅, n₋₄, n₋₃, n₋₂, n₋₁}
        // -n₁                                                    -n₋₁
        // -n₁ -n₂                                           -n₋₂ -n₋₁
        // -n₁ -n₂ -n₃                                  -n₋₃ -n₋₂ -n₋₁
        // -n₁ -n₂ -n₃ -n₄                         -n₋₄ -n₋₃ -n₋₂ -n₋₁
        // -n₁ -n₂ -n₃ -n₄ -n₅                -n₋₅ -n₋₄ -n₋₃ -n₋₂ -n₋₁
        // -n₁ -n₂ -n₃ -n₄ -n₅ -n₆       -n₋₆ -n₋₅ -n₋₄ -n₋₃ -n₋₂ -n₋₁
        //
        // ---
        //
        // This pattern will continue to hold for all (2m+1)-length
        // subarrays, and we will take advantage of it.

        // 「最大的 Subarray 長度」
        var maxSubarrayLength = inputNumbers.Length % 2 == 0 ? inputNumbers.Length - 1 : inputNumbers.Length;

        // 「最小的 Subarray 長度」
        const int minSubarrayLength = 1;

        // 「Subarray 長度的公差」
        const int subarrayLengthCommonDifference = 2;

        // 「輸出值」
        var output = inputNumbers.Sum() * (maxSubarrayLength + minSubarrayLength) * ((maxSubarrayLength - minSubarrayLength) / subarrayLengthCommonDifference + 1) / 2;

        // 「『多餘的項數』的數量變數１」
        var excessiveTermCount1 = 1;

        // 「『多餘的項數』的數量變數２」
        var excessiveTermCount2 = 2;

        // 「『多餘的項數』的數量的差１」
        var excessiveTermCountDifference1 = 1;

        // 「『多餘的項數』的數量的差２」
        var excessiveTermCountDifference2 = 2;

        for (int i = maxSubarrayLength - 2; i > 0; i -= 2)
        {
            output -= inputNumbers[i - 1] * excessiveTermCount2;
            output -= inputNumbers[i] * excessiveTermCount1;
            output -= inputNumbers[inputNumbers.Length - i - 1] * excessiveTermCount1;
            output -= inputNumbers[inputNumbers.Length - i] * excessiveTermCount2;

            excessiveTermCountDifference1 += 2;
            excessiveTermCountDifference2 += 2;
            excessiveTermCount1 += excessiveTermCountDifference1;
            excessiveTermCount2 += excessiveTermCountDifference2;
        }

        return output;
    }
}

參考資料

等差數列

https://en.wikipedia.org/wiki/Arithmetic_progression

• 項數： term
• 差： difference

---

請參考「刷 LeetCode 練習命名」 https://github.com/EngTW/English-for-Programmers/issues/69 😊

[twy30]

這個案例很有趣 🤔

與其它處理「實物」的情景相比，這裡處理的是抽象的數學觀念。

我覺得「命名」在這裡對程式碼讀者的幫助有限，還是要用註解來解釋這個 O(n) 解的演算法的推導過程。

[twy30]

修改了 LeetCode 答案，補上對解題演算法的註解。