这题第一个难点在于一共有n*n-1个数字,如何计算出目标值?
其实只需要任意3个和目标格子构成矩形的值就行了,其他的值并不需要。
因为只考虑这四个的时候,横着2条竖着2条放到这4条线才有影响,如果不是这四条线,等价于没放。
这一步想清楚,耗时可以从1000ms降到100ms。
第二个难点在于如何避免构建二维数组减少空间和读开销?
哪怕目标格子在0_0下标,第一行是一定要全读的。
第一行读完后,要判断待求解是否在第一行,是则结合第二行输出结果,终止后续。
如果不在第一行,一直读到目标时,结合前一行输出结果,终止后续。
这一步想清楚,耗时期望是降低一半。