209. Minimum Size Subarray Sum

問題
雛形
解き方
コード

問題

正の整数配列 nums と正の整数 target が与えられます。部分配列の和が target 以上となるような部分配列の最小の長さを求めてください。そのような配列がない場合は 0 を返してください。

例えば target = 7, nums = [2,3,1,2,4,3] のとき、和が 7 以上となる最も短い部分配列は [4, 3] で長さは 2 です。

雛形

#include <vector>
#include <gtest/gtest.h>
using namespace std;

class Solution
{
public:
    int minSubArrayLen(int target, vector<int> &nums)
    {
        return 0;
    }
};

TEST(TestCase, Case1)
{
    auto s = Solution();
    auto nums = vector<int>{2, 3, 1, 2, 4, 3};
    auto actual = s.minSubArrayLen(7, nums);
    auto expected = 2;
    EXPECT_EQ(expected, actual);
}
TEST(TestCase, Case2)
{
    auto s = Solution();
    auto nums = vector<int>{1, 4, 4};
    auto actual = s.minSubArrayLen(4, nums);
    auto expected = 1;
    EXPECT_EQ(expected, actual);
}
TEST(TestCase, Case3)
{
    auto s = Solution();
    auto nums = vector<int>{1, 1, 1, 1, 1, 1, 1, 1};
    auto actual = s.minSubArrayLen(11, nums);
    auto expected = 0;
    EXPECT_EQ(expected, actual);
}

解き方

しゃくとり法を使います。しゃくとり法については以下の記事をおすすめします。

しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ

区間は半開区間 [left,right) で考え、区間の合計が値が target を超えるまで right を右に移動させます。区間の合計が target を超えたら left を1つ右に移動させます。left が right に追いついてしまったときは right も 1 つ右に移動させ left が right を追い抜かないようにます。

この方針は left を左に移動させると区間の合計値が減り、right を右に移動させると区間の合計値が増えるというのが条件です。今回はの条件では与えられる配列が正の値の配列なのでこの条件を満たします。

以下は target = 7, nums = [2,3,1,2,4,3] の例です。

最初の状態です。区間の合計は 0 です。

2	3	1	2	4	3
L
R

区間の合計が 7 未満なので right を 1 つ右に移動させます。区間の合計は 2 です。

2	3	1	2	4	3
L
	R

さらに right を右に移動させ、区間の合計が 7 以上になるまで繰り返します。この時点で区間の合計は 8 で、区間の長さは 4 です。区間の長さは right - left で求めることができます。

2	3	1	2	4	3
L
				R

区間の合計が 7 以上なので left を 1 つ右に移動させます。区間の合計は 6 です。

2	3	1	2	4	3
	L
				R

区間の合計が 7 未満なので right を 1 つ右に移動させます。区間の合計は 10 で、区間の長さは４です。

2	3	1	2	4	3
	L
					R

区間の合計が 7 以上なので left を 1 つ右に移動させます。区間の合計は 7 です。区間の長さは 3 です。

2	3	1	2	4	3
		L
					R

区間の合計が 7 以上なので left を 1 つ右に移動させます。区間の合計は 6 です。

2	3	1	2	4	3
			L
					R

区間の合計が 7 未満なので right を 1 つ右に移動させます。区間の合計は 9 です。区間の長さは 3 です。

2	3	1	2	4	3
			L
						R

区間の合計が 7 以上なので left を 1 つ右に移動させます。区間の合計は 7 です。区間の長さは 2 です。

2	3	1	2	4	3
				L
						R

区間の合計が 7 以上なので left を 1 つ右に移動させます。区間の合計は 3 です。

2	3	1	2	4	3
					L
						R

left が右端まで移動したので処理を終了します。また、right が右端まで移動していて、区間の合計値が target 未満なら処理を終了できます。これは left が右に移動しても区間の合計値は減る一方で target 以上となることはないからです。

これまでに得られた区間の長さの最小値が求める答えです。区間の合計値が一度も target を超えなかったときは 0 を返すことに注意です。

コード

class Solution
{
public:
    int minSubArrayLen(int target, vector<int> &nums)
    {
        int n = nums.size();
        int right = 0;
        int sum = 0;
        int answer = INT32_MAX;
        for (int left = 0; left < n; left++)
        {
            while (right < n && sum < target)
            {
                sum += nums[right];
                right++;
            }
            if (target <= sum)
            {
                answer = min(answer, right - left);
            }
            if (left == right)
            {
                right++;
            }
            else
            {
                sum -= nums[left];
            }
        }
        if (answer == INT32_MAX)
        {
            return 0;
        }

        return answer;
    }
};

mocoarow

209. Minimum Size Subarray Sum

Table of Contents

問題

雛形

解き方

コード