Algorithm

连续的子数组和

解题思路

【同余定理】 【哈希表】【简化前缀和】

同余定理：如果两个整数 m、n 满足 n-m 能被 k 整除，那么 n 和 m 对 k 同余

即 ( pre(j) - pre (i) ) % k == 0 则 pre(j) % k == pre(i) % k

推导 => pre (i) % k = (a0 + a1 + ... + ai) % k = (a0 % k + a1 % k + ... ai % k ) % k （该推导在简化前缀和的时候有用，说明当前前缀和 % k 不会影响后面的前缀和 % k ）

哈希表 存储 Key ：pre(i) % kValue： i

遍历过程：

1. 计算前缀和 pre( j ) % k

2. 当 pre(j) % k 在哈希表中已存在，则说明此时存在 i 满足 pre(j) % k == pre(i) % k ( i < j )

HashMap 里，已知 Key，可以取到 Value 即 i 的值， 最后 判断 j - i >= 2 是否成立 即可

1. 当 pre(j) % k 不存在于哈希表，则将 (pre(j) % k, j ) 存入哈希表

因在计算 pre(i) = (pre(i-1) + nums[i]) % k 时，pre(i) 只与上一个状态有关

故可以直接用变量 pre 替代数组。 那么 求前缀和 % k 的公式就简化为 题解代码中的 remainder = (remainder + nums[i]) % k;

class Solution {    public boolean checkSubarraySum(int[] nums, int k) {
        int len=nums.length;        if(len<2){            return false;        }
        Map<Integer,Integer> map=new HashMap<>();        map.put(0,-1);        int preNumReminder=0; // 求前缀和的        for(int i=0;i<len;i++){                    preNumReminder=(preNumReminder+nums[i])%k;            if(map.containsKey(preNumReminder)){                int preIndex=map.get(preNumReminder);                if(i-preIndex>=2){                    return true;                }
            }else{                map.put(preNumReminder, i);            }                  }        return false;    }}

Review

关于系统架构，有一些要考虑的因素：哪些是合适的组件/模块 或者可以理解为组成部分，这些组件/模块如何相互配合，以及哪些是正确的权衡。在需要之前 就投资扩展 一般不是一个明智的商业建议；然而，在设计方面进行一些前期思考可以节省未来大量的时间和资源。

本节重点关注几乎所有大型 Web 应用程序都会涉及的一些核心因素：服务、冗余、分区和处理故障。每个因素都涉及选择和妥协，特别是在前一节描述的原则的背景下。为了详细解释这些因素。

主要是介绍了一个图像存储服务，从服务、冗余、存储等角度看如何进行系统架构的设计，以及应对不同问题在架构上取舍和平衡。

主要是读写分离和功能解耦

在某个时候，您可能已经在网上发布过一张图片。对于那些托管和传递大量图片的大型网站来说，构建一种既具有成本效益、高可用性，又具有低延迟（快速检索）的架构是具有挑战性的。

想象一下一个系统，用户可以将他们的图片上传到一个中央服务器，并且可以通过 Web 链接或 API 请求这些图片，就像 Flickr 或 Picasa 一样。为了简单起见，让我们假设这个应用程序有两个关键部分：上传（写入）图片到服务器的能力，以及查询图片的能力。虽然我们当然希望上传效率高，但我们更关心的是当有人请求一张图片时能够非常快速地交付（例如，图片可能会被请求用于网页或其他应用程序）。这与 Web 服务器或内容传递网络（CDN）边缘服务器（CDN 用于在许多位置存储内容，使内容在地理/物理上更靠近用户，从而提高性能的服务器）提供的功能非常相似。

系统的其他重要方面包括：

1. 存储可扩展性：系统需要考虑图像数量方面的存储可扩展性，因为不会限制存储的图像数量。

2. 图像下载/请求的低延迟：用户下载或请求图像时，系统需要提供低延迟的服务，以确保快速响应。

3. 数据可靠性：如果用户上传了一张图片，那么这张图片应该始终存在，系统需要确保图像数据的可靠性。

4. 易于维护：系统应该易于维护和管理，以降低运营和维护的复杂性。

5. 成本效益：由于图像托管没有高利润率，系统需要具备成本效益，以确保在提供服务的同时保持开销的合理性。

在这个图片托管的示例中，系统必须具备明显的快速响应，其存储数据必须具备可靠性，而且所有这些特性都必须具备高度的可扩展性。构建一个小型版本的这种应用程序可能是微不足道的，并且可以轻松地托管在单个服务器上；然而，这对于本章来说并不具备趣味性。让我们假设我们想要构建一个能够像 Flickr 一样成长壮大的系统。

在考虑可扩展的系统设计时，将功能解耦并将系统的每个部分视为具有明确定义接口的独立服务是有帮助的。在实际操作中，以这种方式设计的系统被称为面向服务的架构（Service-Oriented Architecture，SOA）。对于这些类型的系统，每个服务都具有自己独特的功能上下文，与该上下文之外的任何交互都通过一个抽象接口进行，通常是另一个服务的公共 API。

将系统拆解为一组互补的服务使这些部分的运作相互解耦。这种抽象有助于建立服务、其底层环境和该服务的使用者之间的清晰关系。创建这些明确的界限可以帮助隔离问题，同时也允许每个部分独立扩展。这种面向服务的系统设计方法非常类似于面向对象的编程中的设计方法。

快进并假设该服务被广泛使用；这样的情况很容易看出长时间的写入将如何影响读取图像所需的时间（因为这两个功能将竞争使用共享资源）。根据架构的不同，这种影响可能会很大。即使上传和下载速度相同（这对大多数 IP 网络来说并不成立，因为大多数设计至少具备 3:1 的下载速度与上传速度比例），读取文件通常会从缓存中读取，而写入最终需要写入磁盘（在最终一致性的情况下可能需要多次写入）。即使所有数据都在内存中或从磁盘（如固态硬盘）中读取，数据库写入几乎总是比读取慢。

这个设计的另一个潜在问题是像 Apache 或 lighttpd 这样的 Web 服务器通常对能够维护的同时连接数量有一个上限（默认值约为 500，但可以更高），在高流量情况下，写操作可能会迅速消耗所有可用连接。由于读操作可以是异步的，或者可以利用其他性能优化，比如 gzip 压缩或分块传输编码，因此 Web 服务器可以更快地提供读取服务，并在不同客户端之间快速切换，每秒提供的请求数远远超过了最大连接数（对于 Apache 和最大连接数设置为 500，每秒提供数千个读取请求并不罕见）。另一方面，写操作倾向于在上传过程中保持打开的连接，因此在大多数家庭网络上上传 1MB 文件可能需要超过 1 秒的时间，因此该 Web 服务器只能处理 500 个

对于这种瓶颈情况的规划很有道理，可以将图像的读取和写入分离为它们自己的服务，。这使我们能够独立扩展它们（因为我们很可能总是进行更多的读取而不是写入），同时也有助于澄清每个环节发生的情况。最后，这将未来的问题分开，这将更容易排除和解决慢读取等问题。

这种方法的优点在于我们能够独立解决各种问题，我们不必担心在同一上下文中写入和检索新图像。这两个服务仍然利用全局的图像库，但它们可以自由地使用适用于服务的方法来优化自己的性能（例如，排队请求或缓存热门图像，后面会详细介绍）。从维护和成本的角度来看，每个服务都可以根据需要独立扩展，这很好，因为如果它们被合并和混合在一起，就可能会无意中影响另一个服务的性能，就像上面讨论的情况一样。

当您有两个不同的端点时，上述示例通常效果很好（实际上，这与一些云存储提供商的实现和内容传递网络非常相似）。然而，有很多方法可以解决这些类型的瓶颈问题，每种方法都有不同的权衡考虑。

例如，Flickr 通过将用户分布在不同的分片上来解决读/写问题，每个分片只能处理一定数量的用户，随着用户数量的增加，集群中会添加更多的分片（请参阅 Flickr 扩展性的演示，第一个示例中，根据实际使用情况（整个系统中的读写次数）更容易扩展硬件，而 Flickr 则根据用户基数扩展（但要求假设用户之间的使用情况相等，以便有额外的容量）。在前者中，如果其中一个服务出现故障或问题，会导致整个系统的功能中断（例如，没有人可以写入文件），而 Flickr 的一个分片出现故障只会影响那些用户。在第一个示例中，更容易在整个数据集上执行操作，例如更新写入服务以包含新的元数据或在所有图像元数据上进行搜索，而使用 Flickr 架构则需要更新或搜索每个分片（或者需要创建一个搜索服务来汇总这些元数据，事实上这就是他们所做的）。

对于这些系统来说，没有标准答案，但最好回到本章开头的原则，确定系统需求（读取或写入或两者都有，并发级别，跨数据集的查询，范围，排序等等），对不同的替代方案进行基准测试，了解系统将如何失败，并拥有一个坚实的计划来应对故障。在某个时候，您可能已经在网上发布过一张图片。对于那些托管和传递大量图片的大型网站来说，构建一种既具有成本效益、高可用性，又具有低延迟（快速检索）的架构是具有挑战性的。

Tips

Squaretest，它是一款自动生成单元测试的插件，Squaretest 可以 自动生成 Mock 单元测试

我们先来下载一下插件，File——>Settings——>Plugins，搜索 Squaretest，然后 install 就好了，插件安装完成后需要重启一下，重启之后，菜单栏就多了一项 Squaretest

可以通过看这个菜单的最后一项：Generate Test Methods(Help)来看它的一个演示

首先我们打开一个类，这个类就是我们即将要作为实验的类，这个类有 7 个 public 方法，因为 Squaretest 生成的单元测试方法都是只能生成 public 的，当然这也是合理的嘛！毕竟 private 的肯定被 public 调用了

选择第二项后就会弹出一个框看下面这里它自动会识别出当前类需要 Mock 的成员变量，直接点 ok

Share

朴素是富人的权利，或者内心真正富足不需要依赖外在物质和关系的人

我们常常听说 乔布斯、扎克伯格等硅谷精英或者一些超级富豪 不讲究穿着和用品，并成为美谈。就争相模仿。

其实往往弄错了因果关系， 首先他们并不是因为穿着节俭 和朴素而成为富豪的。

往往是因为已经成为富豪或者精英，而不需要在在物质上证明什么。

对于普通人来说，在没有成为大家敬仰的精英前，一个人的外在形象是很重要的。

但并不是为了虚荣 去购买自己能力范围外的奢侈品等，这样反而凸显了内心的空虚，硬撑门面反而容易适得其反。

在自己能力可控范围内，把自己收拾的干净得体，能够体现一个人精神面貌，也能表现出对别人的尊重。 这一点可能代表着合作或者成为别人了解你的机会。