专栏首页Krains1477. 找两个和为目标值且不重叠的子数组 Krains 2020-07-30 09:50:18 动态规划滑动窗口

1477. 找两个和为目标值且不重叠的子数组 Krains 2020-07-30 09:50:18 动态规划滑动窗口

# 题目链接

# 滑动窗口+动态规划

首先看看能否使用双指针

单调性:在[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;
    }
}

# 复杂度分析

  • 时间复杂度:O(n)O(n)O(n),一次扫描
  • 空间复杂度:O(n)O(n)O(n),用了一个dp数组

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CAS Krains 2020-08-25

    其中的关键是 compareAndSet,它的简称就是 CAS (也有 Compare And Swap 的说法),该方法是原子的。

    Krains
  • 运行时数据区 Krains 2020-08-01

    其中虚拟机栈、程序计数器、本地方法栈是线程私有的,也就是说每个线程都会维护自己的一份虚拟机栈、程序计数器、本地方法栈,而方法区和堆是所有线程共享的。

    Krains
  • Lambda表达式

    Java中一切皆对象,因此在Java中函数或者方法无法独立存在,它们不是一个对象,要想像JavaScript进行函数式编程,Java8提出Lambda表达式。

    Krains
  • 浅谈keras中的batch_dot,dot方法和TensorFlow的matmul

    在使用keras中的keras.backend.batch_dot和tf.matmul实现功能其实是一样的智能矩阵乘法,比如A,B,C,D,E,F,G,H,I,...

    砸漏
  • MOBA英雄AI设计分享

    英雄AI的设计原则是:优秀的AI并不要求是尽量的和人表现一致,也不是多么的精准和无懈可击,而是能够和玩家进行很好的交互,提升游戏体验。

    wataloo
  • 使用insert () 在MongoDB中插入数组

    “insert”命令也可以一次将多个文档插入到集合中。下面我们操作如何一次插入多个文档。

    MongoDB中文社区
  • Android 性能优化典范

    2015年伊始,Google发布了关于Android性能优化典范的专题, 一共16个短视频,每个3-5分钟,帮助开发者创建更快更优秀的Android App。课...

    Android架构
  • Leetcode【392、870、881、1090】

    简单题。双指针 i 和 j 分别指向 t 和 s,对于 t 的每一个位置遍历,如果 t[i] 和 s[j] 相同,那么 j 也想后移动找下一个相同的字符。当 j...

    echobingo
  • 虚拟主机如何安装微擎

    魏艾斯博客www.vpsss.net
  • 泛函编程(12)-数据流-Stream

        在前面的章节中我们介绍了List,也讨论了List的数据结构和操作函数。List这个东西从外表看上去挺美,但在现实中使用起来却可能很不实在。为什么?有两...

    用户1150956

扫码关注云+社区

领取腾讯云代金券