经典「前缀和」应用题,以及两大空间优化点|Java 刷题打卡

简介: 经典「前缀和」应用题,以及两大空间优化点|Java 刷题打卡

题目描述



这是 LeetCode 上的 724. 寻找数组的中心下标


Tag : 「前缀和」


给你一个整数数组 nums,请编写一个能够返回数组 “中心下标” 的方法。


数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。


如果数组不存在中心下标,返回 -1 。


如果数组有多个中心下标,应该返回最靠近左边的那一个。


注意:中心下标可能出现在数组的两端。


示例 1:


输入:nums = [1, 7, 3, 6, 5, 6]
输出:3
解释:
中心下标是 3 。
左侧数之和 (1 + 7 + 3 = 11),
右侧数之和 (5 + 6 = 11) ,二者相等。
复制代码

示例 2:

输入:nums = [1, 2, 3]
输出:-1
解释:
数组中不存在满足此条件的中心下标。
复制代码


示例 3:


输入:nums = [2, 1, -1]
输出:0
解释:
中心下标是 0 。
下标 0 左侧不存在元素,视作和为 0 ;
右侧数之和为 1 + (-1) = 0 ,二者相等。
复制代码


提示:


  • nums 的长度范围为 [0, 10000]。
  • 任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。


基本分析



这是一道前缀和的裸题。


只需要用两个数组,前后处理两遍前缀和,再对两个前缀和数组的相同下标进行判别即可。


为了简化数组越界的判断,我们通常会给前缀和数组多预留一位作为哨兵。


这里由于要求前后前缀和。所以我们直接多开两位。


代码:


class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] s1 = new int[n + 2], s2 = new int[n + 2];
        for (int i = 1; i <= n; i++) s1[i] = s1[i - 1] + nums[i - 1];
        for (int i = n; i >= 1; i--) s2[i] = s2[i + 1] + nums[i - 1];
        for (int i = 1; i <= n; i++) {
            if (s1[i] == s2[i]) return i - 1;
        }
        return -1;
    }
}
复制代码


  • 时间复杂度:对数组进行线性扫描。复杂度为 O(n)O(n)O(n)
  • 空间复杂度:使用了前缀和数组。复杂度为O(n)O(n)O(n)


空间优化(常数级别的优化)



当然,我们也可以只处理一遍前缀和。


然后在判定一个下标是否为”中心索引“的时候,利用前缀和计算左侧值和右侧值。


但这只是常数级别的优化,并不影响其时空复杂度。


代码:


class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
        for (int i = 1; i <= n; i++) {
            int left = sum[i - 1], right = sum[n] - sum[i];
            if (left == right) return i - 1;
        }
        return -1;
    }
}
复制代码


  • 时间复杂度:对数组进行线性扫描。复杂度为 O(n)O(n)O(n)
  • 空间复杂度:使用了前缀和数组。复杂度为O(n)O(n)O(n)


空间优化(优化至常数级别)



甚至可以不使用额外空间。


先求一遍总和 total,再使用 sum 记录当前遍历位置的左侧总和。


对于中心索引必然有:sum = total - sum - nums[i] (左边值 = 右边值)


代码:


class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int total = 0, sum = 0;
        // 我们的 nums 处理不涉及并行操作,使用循环要比 Arrays.stream 快
        // total = Arrays.stream(nums).sum(); 
        for (int i = 0; i < n; i++) total += nums[i];
        for (int i = 0; i < n; i++) {
            if (sum == total - sum - nums[i]) return i;
            sum += nums[i];
        }
        return -1;
    }
}
复制代码


  • 时间复杂度:对数组进行线性扫描。复杂度为 O(n)O(n)O(n)
  • 空间复杂度:O(1)O(1)O(1)


总结



这是我使用到的前缀和模板(高频):


class Solution {
    public void func(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
    }
}
复制代码


最后



这是我们「刷穿 LeetCode」系列文章的第 No.724 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
13天前
|
人工智能 Java API
Java与大模型集成实战:构建智能Java应用的新范式
随着大型语言模型(LLM)的API化,将其强大的自然语言处理能力集成到现有Java应用中已成为提升应用智能水平的关键路径。本文旨在为Java开发者提供一份实用的集成指南。我们将深入探讨如何使用Spring Boot 3框架,通过HTTP客户端与OpenAI GPT(或兼容API)进行高效、安全的交互。内容涵盖项目依赖配置、异步非阻塞的API调用、请求与响应的结构化处理、异常管理以及一些面向生产环境的最佳实践,并附带完整的代码示例,助您快速将AI能力融入Java生态。
152 12
|
15天前
|
Java Spring
如何优化Java异步任务的性能?
本文介绍了Java中四种异步任务实现方式:基础Thread、线程池、CompletableFuture及虚拟线程。涵盖多场景代码示例,展示从简单异步到复杂流程编排的演进,适用于不同版本与业务需求,助你掌握高效并发编程实践。(239字)
125 6
|
21天前
|
数据采集 存储 弹性计算
高并发Java爬虫的瓶颈分析与动态线程优化方案
高并发Java爬虫的瓶颈分析与动态线程优化方案
|
21天前
|
安全 Java API
Java SE 与 Java EE 区别解析及应用场景对比
在Java编程世界中,Java SE(Java Standard Edition)和Java EE(Java Enterprise Edition)是两个重要的平台版本,它们各自有着独特的定位和应用场景。理解它们之间的差异,对于开发者选择合适的技术栈进行项目开发至关重要。
100 1
|
2月前
|
安全 Java 编译器
new出来的对象,不一定在堆上?聊聊Java虚拟机的优化技术:逃逸分析
逃逸分析是一种静态程序分析技术,用于判断对象的可见性与生命周期。它帮助即时编译器优化内存使用、降低同步开销。根据对象是否逃逸出方法或线程,分析结果分为未逃逸、方法逃逸和线程逃逸三种。基于分析结果,编译器可进行同步锁消除、标量替换和栈上分配等优化,从而提升程序性能。尽管逃逸分析计算复杂度较高,但其在热点代码中的应用为Java虚拟机带来了显著的优化效果。
63 4
|
2月前
|
设计模式 XML 安全
Java枚举(Enum)与设计模式应用
Java枚举不仅是类型安全的常量,还具备面向对象能力,可添加属性与方法,实现接口。通过枚举能优雅实现单例、策略、状态等设计模式,具备线程安全、序列化安全等特性,是编写高效、安全代码的利器。
|
2月前
|
机器学习/深度学习 人工智能 自然语言处理
Java 大视界 -- Java 大数据机器学习模型在自然语言生成中的可控性研究与应用(229)
本文深入探讨Java大数据与机器学习在自然语言生成(NLG)中的可控性研究,分析当前生成模型面临的“失控”挑战,如数据噪声、标注偏差及黑盒模型信任问题,提出Java技术在数据清洗、异构框架融合与生态工具链中的关键作用。通过条件注入、强化学习与模型融合等策略,实现文本生成的精准控制,并结合网易新闻与蚂蚁集团的实战案例,展示Java在提升生成效率与合规性方面的卓越能力,为金融、法律等强监管领域提供技术参考。
|
2月前
|
存储 监控 数据可视化
Java 大视界 -- 基于 Java 的大数据可视化在企业生产运营监控与决策支持中的应用(228)
本文探讨了基于 Java 的大数据可视化技术在企业生产运营监控与决策支持中的关键应用。面对数据爆炸、信息孤岛和实时性不足等挑战,Java 通过高效数据采集、清洗与可视化引擎,助力企业构建实时监控与智能决策系统,显著提升运营效率与竞争力。
|
2月前
|
存储 人工智能 算法
Java 大视界 -- Java 大数据在智能医疗影像数据压缩与传输优化中的技术应用(227)
本文探讨 Java 大数据在智能医疗影像压缩与传输中的关键技术应用,分析其如何解决医疗影像数据存储、传输与压缩三大难题,并结合实际案例展示技术落地效果。
|
SQL 存储 Java
Java 应用与数据库的关系| 学习笔记
快速学习 Java 应用与数据库的关系。
272 0
Java 应用与数据库的关系| 学习笔记

热门文章

最新文章