We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
There was an error while loading. Please reload this page.
1 parent 1bfff4c commit 4227dcdCopy full SHA for 4227dcd
1 file changed
Hash/1658.Minimum-Operations-to-Reduce-X-to-Zero/Readme.md
@@ -0,0 +1,7 @@
1
+### 1658.Minimum-Operations-to-Reduce-X-to-Zero
2
+
3
+本题的题意是:在nums数组里找a个元素的前缀和,与b个元素的后缀和,使得他们的sum是x,问如果能找到的话,a+b最少是多少?
4
5
+比较直观的算法就是:从右往左遍历b的数目,给定了b,我们就要确定多少个元素的前缀和presum[a],恰好等于x-sufsum[b]。显然,我们可以提前遍历数组来构建所有presum[i]->i的hash表。利用这个hash表就能用o(1)时间快速得到指定前缀和所对应的位置。只要这个位置i小于b,那么i和b就是一对合法的解。
6
7
+最终答案是遍历所有的b,找到i+(n-b)的最小值。
0 commit comments