最小大小子数组总和


难度级别 中等
经常问 亚马逊 Facebook 高盛 谷歌 微软
排列 二进制搜索 两指针

给定一个 排列 一个正整数和和s的num,找到一个连续的子数组num的最小大小,使得其和等于或大于s(给定值)。

使用案列

输入:
nums [] = {2,3,1,2,4,3}
s = 7
输出:
2 {子数组[4,3]的总和为7,并且具有最小长度}

最小大小子数组总和

最小大小子数组总和的朴素方法

解决上述问题的幼稚方法是运行两个嵌套循环,其中外部循环表示子数组的起始索引,内部循环找到总和大于或等于给定总和的子数组的结束索引。
选择最小长度的子数组作为答案。

  1. 将ans初始化为无限。
  2. 对i = 0到n(不包括)运行一个循环,其中n是数组中元素的数量,然后重复步骤3和4。
  3. 将变量sum初始化为0。将布尔变量初始化为false。 对j =(i + 1)到n(不包括)运行一个嵌套循环,并在每次迭代时检查总和是否大于或等于所需总和,如果更大则将其设置为true并最小化更新ans ans和(j – i)的乘积,因为(j – i)是此子数组的长度,因此会跳出循环。 否则将当前元素的值加到总和上。
  4. 如果发现为假,则检查总和是否大于或等于所需总和,如果将其更新为ans且最小值为ans,并且(n – i)为(n – i)是从I到结束的子数组的长度在最后一个元素。
  5. 如果ans的值是无限的,则找不到具有所需总和的子数组,返回0,否则返回and。

JAVA代码

public class MinimumSizeSubarray {
    private static int findMinimumSizeSubarray(int[] nums, int s) {
        int n = nums.length;
        int ans = Integer.MAX_VALUE;
        // Outer loop denotes starting index
        for (int i = 0; i < n; i++) {
            int sum = nums[i];
            boolean found = false;
            // Inner loop finds the ending index
            for (int j = i + 1; j < n; j++) {
                if (sum >= s) {
                    // Subarray found
                    int length = j - i;
                    ans = Math.min(ans, length);
                    found = true;
                    break;
                }

                // Add the current value to sum
                sum += nums[j];
            }

            if (!found) {
                // This handles the case of subarray from i to last
                if (sum >= s) {
                    int length = n - i;
                    ans = Math.min(ans, length);
                }
            }
        }
        
        // Subarray with required sum is not found
        if (ans == Integer.MAX_VALUE) {
            ans = 0;
        }
        
        return ans;
    }

    public static void main(String[] args) {
        int nums[] = new int[] {2, 3, 1, 2, 4, 3};
        int sum = 7;
        
        int minSize = findMinimumSizeSubarray(nums, sum);
        System.out.println(minSize);
    }
}

C ++代码

#include <bits/stdc++.h>
using namespace std;

int findMinimumSizeSubarray(int *nums, int s, int n) {
    int ans = INT_MAX;
    // Outer loop denotes starting index
    for (int i = 0; i < n; i++) {
        int sum = nums[i];
        bool found = false;
        // Inner loop finds the ending index
        for (int j = i + 1; j < n; j++) {
            if (sum >= s) {
                // Subarray found
                int length = j - i;
                ans = std::min(ans, length);
                found = true;
                break;
            }
            // Add the current value to sum
            sum += nums[j];
        }
        
        if (!found) {
            // This handles the case of subarray from i to last
            if (sum >= s) {
                int length = n - i;
                ans = std::min(ans, length);
            }
        }
    }
    
    // Subarray with required sum is not found
    if (ans == INT_MAX) {
        ans = 0;
    }
        
    return ans;
}

int main() {
    int nums[] = {2, 3, 1, 2, 4, 3};
    int sum = 7;

    int minSize = findMinimumSizeSubarray(nums, sum, 6);
    cout<<minSize<<endl;
    
    return 0;
}
2

最小大小子数组总和的复杂度分析

时间复杂度= 2
空间复杂度= O(1) 
其中n是数组中元素的数量。

最小大小子数组总和的最佳方法

解决该问题的更好方法是使用两个指针ptr1和ptr2,其中ptr1代表子数组的起始索引,而ptr2代表结束索引。

算法

  1. 将ptr1和ptr2初始化为0(零),并将变量sum初始化为0(零)。
  2. 当sum的值小于所需的sum时,将存在于ptr2的值相加即可求和并将ptr2向前移动。
  3. 当sum的值大于或等于所需的sum时,更新最小子数组长度,并从sum中删除ptr1上存在的值,然后将ptr1向前移动。
  4. 当ptr2小于给定数组的长度时,重复步骤3和步骤1。
  5. 如果没有子数组具有所需的总和,则返回0,否则返回最小长度子数组的长度。

JAVA代码

public class MinimumSizeSubarray {
    private static int findMinimumSizeSubarray(int[] nums, int s) {
        int n = nums.length;
        // Initialize ptr1, ptr2 and sum as 0
        int ptr1 = 0, ptr2 = 0, sum = 0;
        int ans = Integer.MAX_VALUE;

        // While ptr2 is less than n
        while (ptr2 < n) {
            // While the sum is less than s, add value present at ptr2 to sum and move ptr2 ahead
            while (sum < s && ptr2 < n) {
                sum += nums[ptr2++];
            }

            // While sum greater than or equals to s, update the minimum subarray length and remove value
            // present at ptr1 from sum and move ptr1 ahead
            while (sum >= s && ptr1 < n) {
                ans = Math.min(ans, ptr2 - ptr1);
                sum -= nums[ptr1++];
            }
        }

        // Subarray with required sum is not found
        if (ans == Integer.MAX_VALUE) {
            ans = 0;
        }

        return ans;
    }

    public static void main(String[] args) {
        int nums[] = new int[] {2, 3, 1, 2, 4, 3};
        int sum = 7;

        int minSize = findMinimumSizeSubarray(nums, sum);
        System.out.println(minSize);
    }
}

C ++代码

#include <bits/stdc++.h> 
using namespace std; 
int findMinimumSizeSubarray(int *nums, int s, int n) { 
  // Initialize ptr1, ptr2 and sum as 0 
  int ptr1 = 0, ptr2 = 0, sum = 0; 
  int ans = INT_MAX; 
  // While ptr2 is less than n 
  while (ptr2 < n) { 
    // While the sum is less than s, add value present at ptr2 to sum and move ptr2 ahead 
    while (sum < s && ptr2 < n) { 
      sum += nums[ptr2++]; 
    } 
    // While sum greater than or equals to s, update the minimum subarray length and remove value 
    // present at ptr1 from sum and move ptr1 ahead 
    while (sum >= s && ptr1 < n) { 
      ans = std::min(ans, ptr2 - ptr1); 
      sum -= nums[ptr1++]; 
    } 
  } 
  // Subarray with required sum is not found 
  if (ans == INT_MAX) { 
    ans = 0; 
  } 
  return ans; 
} 
int main() { 
  int nums[] = {2, 3, 1, 2, 4, 3}; 
  int sum = 7; 
  int minSize = findMinimumSizeSubarray(nums, sum, 6); 
  cout<<minSize<<endl; 
  return 0; 
}
2

最小大小子数组总和的复杂度分析

时间复杂度= O(N) 
空间复杂度= O(1)
其中n是数组中元素的数量。

參考資料