现代人意义的丧失

《心理学与人类困境》读书笔记 2

现代人意义的丧失所描述的是现代人作为个体在面对巨大社会机器时所产生的无力感,是“即使我知道我是谁,我作为一个个体也产生不了什么影响”这种心态的描述。

个体无意义的情况在变动的历史时期尤其明显。当旧的价值倡导不再具有说服力,传统已经不再可行,个体就会体验到要在他的世界中找到自我存在非常困难。除了倡导的方式的落后等原因,更多的是因为变革时期价值坐标的混乱。

当坚守传统价值却并不能带来幸福,当越来越多不符合传统价值观念的人却获得了更大的成功,人们便会对原有的价值观产生怀疑。很多伟大的文学作品所描述的正是人在巨大的变革时代的无力感,典型的如《白鹿原》。即使在现代,我们也能体验到这种变动的冲击,比如同川普的当选对许多坚持移民自由平等信念的人的打击。

个体的无意义感来自个体价值在庞大的社会机器中无法得到体现。西方文化一直教育学生个人的自我是有价值的,是有意义的,甚至民主制度本身也是对这种个人价值认同的体现,但当学生进入到庞大的社会,感受到自己仅仅是庞大社会中极小的一部分,个体的影响力被完全稀释的时候,个体无意义感就产生了。

个体无意义感的直接后果是带来反抗:对主流价值的反抗。本质上却是希望通过反抗的方式获得更多的关注:通过反抗行动,我迫使非个人的权威或者太系统化的体系看到我,认可我,承认我现在的样子,考虑我的力量。

更严重的后果是作为人的责任感的削弱。这也可以用来解释为什么组织中责任感随着层级的降低而削弱:除了直接经济利益的激励的削弱,个人无力感到的增加是最重要的原因。一个人在组织中发挥的职责和影响越小,他越对自己的行为产生无意义感,也就越难以产生责任感。另一个结果是情感冷漠,更进一步的是个人意识的退缩,非个人的、技术力量大的急速增长更进一步挤占了人的意识空间,人放弃对于潜能的追求,退缩到自我的世界。

个体意义的丧失在组织人的现象得到非常具体的体现:只要人放弃了作为个人的个性和身份而进入到一个组织之中,他反而可以获得更大的成功。这是由于集体化和专业化的必然结果,要在巨大的体系中获得成功,人必须放弃他作为个人的特色。

人类困境的产生

《心理学与人类困境》读书笔记 1

困境对应英文delima, 在中文被翻译为:两难境地。字面上困境所表达的意思是,一个无法解决的问题,如果其中一个困难没有为难你,那么另一个困难必然会为难你。在《心理学与人类困境中》,困境是指人类无法逃脱的,截然相反的情况与自相矛盾的境地。为了逃避某一方面,困境会导致僵局,障碍以及在另一个方面的狂乱的过度发展。

这本书所要重点讨论的不是物质的困境,而是现代世界人所面临的一系列精神困境:比如认同感的丧失,焦虑以及对于自由和责任等概念的困惑。

人类的这些精神困境是如何产生的呢?人的困境源自于人们可以同时见自己体验为主观和客观的能力。注意,并不是说人类的困境就是这种能力,而是说人类困境的产生源自于这种能力。作为主观的个体和作为客观的个体之间体验的冲突就带来了这种精神困境。

以人的对自身价值的认识为例,从主观的角度观察,每个人的情绪都是丰富多彩,每个人的人生体验都是独一无二的,从这个角度说,每个人的价值都是独一无二的。但若从客观的角度观察,每个人却又都是微不足道的,他的人生不过是万千平凡的人生中的一个,他的喜怒哀乐、个体体验是如此个人化,以至于是无法被理解也不值得被理解的。从这个角度说,每个人的价值都是孤独、微不足道的。人的可贵之处在于,他可以从这两个方面观察到自己,认识到自己处于两种不同的价值定位中。而人的渴望被理解、被关注的愿望则会不断试图想要将这两种价值统一起来,从而形成内在的张力和焦虑。人的意识也并不是固定在一端,而是不停的在两端之间摇摆。当他发现自己的努力并不能够将二者拉近的时候就会产生一种无法突破的困境感。

另一个的例子是人的自由与命运(freedom and destiny)的冲突。人是自由的,他的思想是自由的, 他可以意识到自己的生存和死亡,他既可以认识到他所生存的世界也可以意识到他的生存本身。但另一方面,人也是不自由的,不管是外在的物质、身体的限制,还是内在的智力、非理性的限制,都将人囚禁在一个看不见的牢笼之中。人甚至会对他的自由意志感到怀疑:我们所做的选择是完全出于自由意志还是有一只看不见的手在安排?人对于自由和命运的体验正来源于他可以从主观和客观两个角度观察自己的存在。如果人是自由的,那么他的努力是有意义的,他的决定也是自由的,他可以选择成为自己想要成为的人。但如果人是被注定的,那么他的所有努力都是徒劳的没有意义的。人的意识不断的在这两种思想之间摇摆徘徊,并因此产生创造的勇气和自我否定焦虑,精神的困境也由此产生。

这些困境是不是只是一无是处?并不是的,尽管人面令无数艰难的冲突和选择,但正是通过建设性的面对这些自相矛盾的境地所导致的紧张情绪,人类才构建了文化与文明。

认识到人处在困境中对我们有什么好处呢?我想,最大的好处在于,我们将可以或多或少使自己放松下来。人最大的焦虑往往正是来自于精神的困境,我们竭尽全力想要突破这些困境,却常常发现无法取得任何进展。认识到困境是人生的常态,承认无法突破困境更是一种人生常态,对于我们来说是一种极大的安慰。这样的认识使我们重新审视自己的人生,放弃对于没有困境的人生的幻想。正如接受人生的不完美一样,在此认识的基础上我们才有可能重新出发。

价值和价值观

价值观是什么?根据维基百科的定义:价值观是一种处理事情判断对错,做选择时取舍的标准。有益的事物才有正价值。所以简单的说,价值观这个概念的核心在于:它是一种标准,它主要应用于两种场景:判断对错做出选择。如果我们把价值观看做一个整体,那么把它拆解开,其组成元素可以称为价值

我们首先区分价值价值观的概念。每样事物都有价值:比如他人的认同是一种价值,思想和行动的独立也是一种价值,帮助他人是一种价值,自私也是一种价值。仅仅把这些价值机械的组合在一起并不构成价值观,价值观是对这些价值的排列和取舍,正如同它在两种应用场景中的体现:判断对错和做出选择。

判断对错的困难在于对价值的排列。人对于事物的争议正在于进入排列的价值以及对这些价值的排列不同。只要看一看人们对于同一件事物有多少不同的看法就知道人们关于价值的排列有多么不一致。即使是对于个人,进行价值判断也不是一件容易的事情,其困难性在于没有什么价值是绝对的。

选择的主要困难在于取舍。经济学的一大原则是:人面临选择。因为人的资源,尤其是时间资源有限,人的选择常常具有排他性,选择的另一层含义是放弃,选择什么也就是不选择其他的什么。当然,选择的困难不至于对价值进行取舍,还在于如何确定我们所作出的选择最终能带给我们所期待的价值。比如如果认为追求财富是进行某项选择时候的最高价值,那么如何能保证我们进行的选择会为我们带来财富呢?当然这属于另一个更大的话题。

关于价值观我们还需要明白两点:

  • 价值观具有多种维度。比如,个人的价值观,集体的价值观。
  • 价值观是动态的。人的价值观不是一成不变的,不同时期的人其价值观也是不一样的。
  • 价值观具有情境性。人在不同的情境下对于价值的排列也是不同的。

理解这些之后我们就更容易原谅人性中的模棱两可和反复无常。

Machine Learning: Simple Linear Regression

Let’s first take a look at simple linear regression.

First let’s start with an open question: imagine you can get all the information you need, how do you predict the selling price of a house?

I believe you might consider the following factors:

  • House size
  • House location
  • House making year
  • Location of the house
  • Other features.

General machine learning steps

If we can the these information of many house, then we are able to predict the selling price of this house. A simple linear regression is doing exactly the same thing: it take the feature information of existing house as input, then try to predict the prices of another house.

Then there are a few general steps for a prediction work that are applied in the above process, including:

  • Feature engineering: trying to find or create features that make machine learning algorithm work.
  • Model selection: try to find the best model that can interpret the given question.
  • Training: once you get the model, you need to train the model to make sure the model is customized for your problem
  • Testing: you also want to test whether the given model over customized or not by testing it with data sets beyond training data.
  • Prediction: use the given model, make prediction for the problem you want to talk about.

Let's look back to the house price prediction issue. Assume we only consider one feature: square feet of the house. And we may assume the function of size to price is y = ax + b.
The next question is how to determine: a and b.

Cost function

One principle or standard that help us determine a and b is that:
If we define the error of prediction as (yi - f(Xi))^2, then for all training data set, a and b should minimize SUM(yi - f(xi)). Then we call (yi - f(xi))^2 cost function. It is used to gauge the cost of using a particular model.

Then we come the following questions:

  • Of what value should a and b be initiated?
  • How should we change a and b after we now the cost of using existing a and b?
  • How do we know whether we can find the optimal a and b?
    To answer the first question: it does not matter what the initial value of a and b we choose.

Gradient descent

For the second question: how should we move to reach the optimal destination?
We want to know the concept of gradient: the gradient point in the direction of greatest rate of increase of the function. Which means, we are able to find the min or max of a function by following the gradient direction. For example, let's say we have a single variable convex/concave function. For concave function, we can find the max through hill climbing; while for concave function, we can find the minimal value through hill descent. For multi variable functions, it is essentially the same, so we are able to find the min and max as well.

When we do hill climbing or hill descent, one thing we need to consider is the step size: where is the next step if we did not find the max/min value.

There are two approaches for step size choose:

  • Fixed size
  • Decreasing step size.

For the third questions: when should we stop moving? In theory, when converged, gradient should be zero, while in practice, the move stops when the gradient is less than the threshold.

Then it becomes a math question:

  • How do we compute gradient for multiple variable function?
  • How do we compute gradient for multiple dimension vectors?

We will talk about all the general steps mentioned and un-mentioned later, including the detail of gradient descent.

经济学的数学原理:总成本,边际成本,边际收益和市场均衡

经济学当中涉及到大量的数学原理,这篇文章只专注于其中关于成本和收益的一些简单概念,意在从数学的角度阐释下面的问问题:

  • 平均总成本曲线的形状为什么是U行的?
  • 为什么边际成本曲线和平均总成本曲线总是相交于平均总成本最低点?
  • 为什么长期价格等于企业的平均总成本?
  • 为什么竞争企业的边际成本等于价格?
  • 为什么竞争市场中的企业运行在有效规模?

概念

首先让我们厘清关于成本的若干概念:

  • 边际产量:增加的一单位投入所引起的产量增加
  • 边际产量递减:一种投入的边际产量随着投入增加而减少的特征,注意是边际产量而不是总产量。
  • 固定成本(FC):不随着产量而变动的成本。指的是即使企业不生产也要发生的成本。
  • 可变成本(VC):随着产量而变动的成本。
  • 总成本(TC):固定成本加上可变成本。
  • 平均总成本(ATC):总成本除以产量。
  • 边际成本(MC):额外单位产量所引起的总成本的增加。
  • 有效规模:使平均总成本最小的产量。

平均总成本和边际成本

为什么平均总成本是U形的?

  • 总成本中包括固定成本和可变成本:TC = FC + AC。
  • 平均总成本包括平均固定成本和平均可变成本:ATC = AFC + AVC。
  • AFC短期内持续下降,长期因为需要替换原有设施等原因可能回升。
  • AVC持续上升,并且随着边际产量递减的效应而加速上升。
  • ATC 的变化趋势由AFC的下降和AVC的上升哪一个占据主导地位决定。
  • 初始的时候,AFC的下降占主导地位,因此ATC下降。
  • 超过一定均衡数量之后,AVC的上升占据主导地位,因此ATC开始上升。

为什么边际成本曲线和平均总成本曲线在平均总成本曲线的最低点相交?

边际成本 = 总成本变动量/产量变动量,MC = d(TC)/d(Q)
平均总成本 = 总成本/产量,ATC = TC/Q

数学推论过程如下:

假设固定成本 F
可变成本V(x)
ATC = (F + V(x))/x
MC = d(V(x)) / d(x)
ACT 最低点:
d(ACT)/d(x) = d((F + V(x))/x)/d(x) = 0
得到 xd(V(x))/d(x) = F + V(x)

下面举例说明:

假设 TC = Q^2 + 9Q + 5
则 ATC = TC / Q = Q + 9 + 5/Q
    MC = d(TC)/d(Q) = 2Q + 9
令 ATC = MC:Q + 9 + 5/Q = 2Q + 9 得到:Q = 5^(1/2)。
对ATC进行进一步微分:
d(ATC) = d(Q + 9 + 5/Q)) = d(Q + 9 + 5 * Q^(-1)) = 1 - 5 * Q^(-2)
令:1 - 5/Q^2 = 0,Q = 5^(1/2)。
验证了ATC在最低点正式ATC与MC的焦点的理论。

那么如何从直观上理解呢?

  • 当边际成本小于平均成本的时候,平均下降,因为新增加的产出都是以低于平均成本的价格生产的。
  • 当边际成本大于平均成本的时候,平均成本升高,因为新增加的产出都是以高于平均成本的价格生产的。
  • 只有当边际成本等于平均成本的时候,平均总成本才会保持不变,也就是最低点。

从上面的得到的另一个重要推论是:边际成本曲线和边际总成本曲线相交于有效规模。也因此带来两个概念:

  • 规模经济:长期平均总成本随着产量的增加而减少。
  • 规模不经济:长期平均总成本随着产量的增加而增加。

需要知道,导致规模经济的原因是生产水平的提高和工人的专业化,而规模不经济的产生原因主要在于大型组织中存在的协调问题。

边际收益

为什么竞争企业使得价格等于边际成本?

上面的问题等效于:为什么利润最大化的生产水平时,边际收益和边际成本正好相等?

  • 如果边际收益大于边际成本,则企业会提高生产以获得更多的利润
  • 如果边际收益小于边际成本,则企业会降低生产以避免因此造成的损失,总利润也会增加。

要注意到的是,在竞争市场的假设中,企业的边际收益就是市场价格,因此企业利润最大化的生产水平正是其边际成本等于市场价格的水平。注意这里的变量值包括边际收益,也就是市场价格和边际成本,并不包含平均总成本。

为什么竞争市场长期价格等于平均总成本?

我们知道,企业的供给曲线由平均可变成本决定,而长期供给曲线由平均总成本决定。利润 = (P – ATC) X Q。设想下面的两种情况:

  • 如果价格大于平均总成本,则变得有利可图,就会有企业进入市场,从而导致价格下降,利润下降。
  • 如果价格小于平均总成本,则会由企业面临亏损退出,从而导致产量下降,价格上升,利润提高。

这两种趋势的平衡发生在当利润为零的时候。但是需要注意,这里的利润是经济利润,而不是会计利润。经济利润中包含了机会成本,因此经济利润为零的时候,会计利润仍然可能是正的。

竞争市场均衡推论

前面我们得到这样几条结论:

  • 边际成本和长期总成本相交与长期总成本的最低点。
  • 企业在长期总成本最低的时候是有效规模。
  • 竞争的企业使得价格等于边际成本。
  • 竞争的市场使得价格等于平均总成本。

所以我们可以得到一个重要推论

在有自由进入与退出时,竞争市场长期均衡一定是企业在其有效规模时运行。

引用

税收的哲学:效率和平等

工作之后,我们所切身关心的问题包括:

  • 我们交了多少税?
  • 我们为什么要交这么多税?
  • 我们怎样才能少交税?

这篇文章里,我想要重点讨论第二个问题:我们为什么要交这么多税?

我们知道,为了维持公共机构和公共服务的运转,税收是必不可少的,“税收是我们为文明社会付出的代价”。根据社会契约的思想,每个人让渡出一部分的个人权利来组成一个政府,从而保护自己的财产等权利,税收可以视作是这让渡出的一部分权利。那么如何确定每个人应该缴纳税款的量呢?怎么样的税收制度才是有效率的?

税收的效率

每种税收的办法都有其成本。成本之一来自税收改变了人们的决策所引起的无谓损失,其二来自税收的管理成本。我们知道税收的存在改变了人们的行为。比如,如果对个人所得征收极高的所得税,那么人们的工作热情势必降低,因为税收等于降低了实际收入。税收的管理成本包括花在收税和缴税上的所有成本。比如要维持整个征税系统的运作所需要的成本,每个人每年报税所需要花费的成本等。

那么怎样降低税收的成本以提高税收的效率呢?其中一项策略是在不同的环节征税从而取得不同的效果,比如在收入环节征税会直接一直人们的工作热情,但是在消费环节征税则不会,从而有可能降低税收的无关损失。从税收的管理成本上看,简化税收的流程和设计,可以降低税收的管理成本。

税收的平等

我们都同意,税收制度应该是平等的,但是什么才算是平等的税收?怎么判断一项税收制度是否平等呢?这里有两种主要的思想。

首先是收益原则的思想,即根据从公共服务中获益的程度来决定税收的数量。税收的目的是为了提供公共服务,那么我们很自然的联想到,一个人从公共福利中得到多少好处,他就应该提供多少税收。基于这种思想我们有时可以推论出富人应该缴纳更多的税赋。比如评估财产保护这项公共服务,那么富有的人肯定会出更高的价格,因此我们可以认为在享受相同的财产保护的服务的时候,富人从中得到的好处更多。

另一种是能力原则的思想。这种思想认为,应该根据一个人的支付能力来纳税。也就是说,支付能力大的人付出的更多,支付能力形同的人付出的数额相同。前一种称为纵向平等,后一种称为横向平等。

但是,从个体的角度来说,收益原则是最直接的心理依据。比如,觉得自己交税太多的人往往是认为自己交税的成本远远大于享受到的社会福利,或者认为社会福利被转移支付到了较为穷困的人手上,是对自己的不公平。

如何衡量税收是否平等?

要衡量税收是否平等,我们首先需要知道税收的负担最重落在了谁的身上,也就是说,最后是谁来支付税收的实际成本?与我们的直觉相反,并不总是收到税单的人承担了税收的实际成本。比如,选民们总是渴望减少自己的税收,或者宁愿税收由非个人化的公司来支付。但实际上,虽然公司所得随不在员工的工资单上出现,但会导致公司的成本增加,反过来可能导致员工的福利降低,从而使税收的实际成本转移到了普通员工的身上。因此,衡量税收的负担要考虑到税收的间接效果,而不是通过直接比较税收的账单来得到。

权衡取舍

税收的效率和平等是有冲突的。比如出于平等的考虑,我们会对富人收更多的税,但这损害了富人们在经济上的积极性,从而带来更大的无谓损失。不同阶层出于自己不同的利益,也会推动税收制度向这两个方向变动,最典型的例子比如里根总统的减税计划。

税收的社会干预作用

除了作为提供公共服务的收入来源,税收作为一项政策工具还可以用于进行社会干预和管理。比如如果对储蓄利息征收高所得税,就等于降低了银行储蓄的实际利率,人们就会将更多的钱用于消费和投资。比如,对遗产征收高额度的税赋有利于降低财富的代季积累效应。也就是说,遗产税的存在使得后代较少的受益于父辈积累的社会资源,从而降低与同辈竞争时的优势,进而促进社会公平。当然,代价是牺牲了经济上的效率。

Sliding Window: Minimal Window of Array

Sliding Window

Sliding window is a common seen technique in solving algorithm, it has a few elements:

  • Window start and end
  • Status of elements in the window
  • Window extends to the right according to the status
  • Window shrinks to the right according to the status
  • Window stops moving at certain condition.

sliding-window-page-1

Before we discuss sliding window algorithm, we must understand:

  • Any problem can be solved by sliding window can be solved by enumerating all possible combinations
  • Sliding window skipped some of the combinations to speed up

So the key to sliding window application is to prove:

No need to check the skipped combinations.

Let’s take a look at two questions and their solution and then come back to the discussion of sliding window.

Minimum Size Subarray Sum problem

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

Observations

From the description we have the following observations:

  • The elments are positive: sum of window increase/decrease as we expand/shrink window
  • The condition is sum >= s: when sum >= s we should expand, then shrink
  • Target at minimum subarray size: then have to shrink then window as much as possible

Looks like sliding window algorithm can be applied to this problem, but we have to answer the following questions:

What combinations are skipped?

We may simply the example above: [2,3,1,2] and s = 7
The following are combinations that will be visited:

  • [2]
  • [2, 3]
  • [2, 3, 1]
  • [2, 3, 1, 2]
  • [3, 1, 2]

The combinations that are skipped are:

  • [3, 1]
  • [1]
  • [1, 2]
  • [2]

And the [3, 1] was skipped when we shrink the window at [2, 3, 1, 2].

Is it correct to skip these combinations?

Consider about the target: sum >= s.

  • If [3, 1] >= s, then when the window grows from [2, 3] to [2, 3, 1] it will stop there because sum([2, 3, 1]) > sum([3, 1]) > 2
  • If it stopped, [3, 1] will be visited
  • But since it didn’t stop, [3, 1] is < s, no need to visit.

To make this prove more generic:

  • Assume the window stopped at [i, j]
  • Then j is the first element from i to n that makes sum(i, j) >= s
  • In another way, any sub window [i, k] where k < i will make sum(i, k) < s, so these sub window can be skipped.

Algorithm

Based on the discussion above, we come to the following algorithm:

while right < n:
    sum += num[right ++]
    while (sum > s):
        minLen = Math.min(minLen, right - left)
        sum -= num[left++]

Notice how the important principle we discussed in the beginning are applied in this algorithm:

  • Window: Use left and right boundary to represent a window
  • Stop condition: right boundary stops at the end
  • Status update:update status of window every time the window moves
  • Move condition: expand the window when the status did not mets requirement
  • Move condition: Shrink the window while the status meets requirements

Implementation

The following is the implementation of the algorithm:

public int minSubArrayLen(int s, int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int windowSum = 0;
    int minLen = nums.length + 1;
    for (int left = 0, right = 0; right < nums.length; right ++) {
        windowSum += nums[right];
        while (windowSum >= s) {
            minLen = Math.min(minLen, right - left + 1);
            windowSum -= nums[left ++];
        }
    }
    return minLen == nums.length + 1 ? 0 : minLen;
}

Minimum Window Substring problem

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the empty string “”.

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Observations

We have the following observation about the problem:

  • Target at finding the minimal window that contains all characters in T
  • Sliding window characters can be applied to it: expand the window will increase the occurrence of certain character.

What combinations are skipped?

Let’s also simply the given examble to ADBEC, the following are combinations visited:

  • [A]
  • [A, D]
  • [A, D, B]
  • [A, D, B, E]
  • [A, D, B, E, C]
  • [D, B, E, C]

The combinations that are skipped are:

  • [D, B]
  • [D, B, E]
  • [B]
  • [B]
  • [B, E]
  • [B, E, C]

[D, B, E] are skipped when we shrink from [A, D, B, E, C] to [D, B, E, C].

Is it correct to skip these combinations?

The correctness can be proved similar to the process in the above question:

Let’s assume at window [i, j] it meets the targeting requirement, then the implication is that it does not meet the requirement at any sub window [i, k] where k < j. When any combination of these sub windows can be safely skipped.

Algorithm

The key is to find a way to:

  • Record the status of the window

Use a char map to record the occurrence of each character in the window.

  • Indication of the window meets requirement

This indication must be able to grow or decrease incrementally. A special count works

  • The count increase only when stats[ch] < target[ch], decrease when stats[ch] < target[ch]

where stats[ch] is the occurrence of ch in the window and target[ch] is the target occurrence of ch.

Implementation

The algorithm is very similar to the question above, the implementation is as below:

public String minWindow(String s, String t) {
    char[] tCh = new char[128];
    char[] sCh = new char[128];

    for (char ch : t.toCharArray()) {
        tCh[ch] ++;
    }

    String ret = "";
    int count = 0;
    int minWindowSize = Integer.MAX_VALUE;

    for (int left = 0, right = 0; right < s.length();) {
        char chRight = s.charAt(right ++);
        if (sCh[chRight]++ <= tCh[chRight]) {
            count ++;
        }

        while (count == t.length()) {
            if (right - left < minWindowSize) {
                minWindowSize = right - left;
                ret = s.substring(left, right);
            }

            char chLeft = s.charAt(left++);
            if (sCh[chLeft]-- < tCh[chLeft]) {
                count --;
            }
        }
    }

    return minWindowSize == Integer.MAX_VALUE ? "" : ret;
}

Sliding window application principle

Sliding window characteristics:

  • Sliding window has a start and end
  • Sliding window has status that indicate the status of the window
  • Sliding window grows/shrink toward one direction

Sliding window application principles:

  • Sliding window skipped some combinations to improve efficiency, to use sliding window needs to prove these combinations can be skipped.

In terms of implementation, here is the key ideas:

  • Use nested loop to move window: outer loop to expand the window, inner loop to shrink the window
  • The outer loop stop condition is the right boundary meets array end
  • The inner loop stop condition is the status of the window meets requirement, as long as it still meets requirement, shrink the window as possible.

Questions and follow ups:

  • If we change the question to Maximum Size subarray, does the sliding window algorithm still work?

Maximum size subarray does not need to apply sliding window: find out the sum of the entire array, if it meets requirements, it is the max window, otherwise no sub window works.