首先看看能否使用双指针
单调性:在[i, j]
的区间和是小于等于target的条件下,即sum(i,j)>=targetsum(i, j)>=targetsum(i,j)>=target,假设窗口[i, j]
满足条件且是以j结尾的最大区间,如果此时j往后移了一位,因为arr数组所有元素是大于0的,因此sum(i,j+1)>sum(i,j)sum(i, j+1)>sum(i,j)sum(i,j+1)>sum(i,j),如果i往前移动一位,如果此时还满足区间和小于等于target,sum(i−1,j+1)>=targetsum(i-1, j+1)>=targetsum(i−1,j+1)>=target,那么以j结尾的最大区间就应该为[i-1, j]
,此时就与假设条件矛盾了,即满足单调性,可以使用双指针。
如果数组元素都大于0,可以使用双指针,如果可正可负或者有0就不能使用。
如果不能使用双指针,那么可以使用前缀和加哈希的方式快速找到满足条件的区间。
如何选取两个互不重叠的区间且它们长度之和最小呢?
使用f(j)f(j)f(j)表示当前j以及j之前的满足条件的最小区间长度,假如当前区间为[i, j]
,状态更新规则为:
f(j)=min(f(j−1),j−i+1),ifsum(i,j)=targetf(j)=min(f(j-1), j-i+1),if\ sum(i,j)=target f(j)=min(f(j−1),j−i+1),ifsum(i,j)=target
答案更新规则:
ans=min(ans,f(i−1)+j−i+1)ans=min(ans, f(i-1)+j-i+1) ans=min(ans,f(i−1)+j−i+1)
表示当前以j结尾的满足条件的区间长度与i-1之前的最小的区间长度之和,这样就能满足两个窗口不重叠且长度之和最小。
class Solution {
public int minSumOfLengths(int[] arr, int target) {
int n = arr.length;
int[] dp = new int[n];
// 注意不能设置为最大值,因为相加会溢出
Arrays.fill(dp, Integer.MAX_VALUE / 2);
int ans = Integer.MAX_VALUE;
for(int i = 0, j = 0, sum = 0; j < n; j++){
sum += arr[j];
while(i <= j && sum > target){
sum -= arr[i++];
}
// 找到满足条件的一个区间
if(sum == target){
dp[j] = j - i + 1;
if(i != 0){
ans = Math.min(ans, dp[i-1] + j - i + 1);
}
}
if(j != 0)
dp[j] = Math.min(dp[j], dp[j-1]);
}
return ans > arr.length ? -1 : ans;
}
}