[1658] Minimum Operations to Reduce X to Zero

嗯.......

要找從左邊或右邊連續的加總等於 X的最短長度

反過來說，也就是找中間的加總等於 total sum - x 的最長

所以就用前兩天寫的 [209] Minimum Size Subarray Sum 差不多概念(吧）

覺得麻煩的題目>< 怎麼一直寫錯呢屋屋

int minOperations(int* nums, int numsSize, int x){

int currSum=0;

int total=0;

for (int i=0;i<numsSize;i++)

total += nums[i];

if (total== x)

return numsSize;

int target = total - x;

int left, right,diff;

left=right=diff=0;

int max = INT_MIN;

while (right < numsSize)

{

currSum += nums[right];

while (currSum >=target && left <= right)

{

if (currSum == target)

{

diff = right - left +1;

if (diff > max)

max = diff;

}

currSum -= nums[left++];

}

right++;

}

if (max == INT_MIN)

return -1;

return numsSize-max;

}

把一些assignment改一改可以變快一點點QQ

int minOperations(int* nums, int numsSize, int x){

int currSum=0;

int total=0;

for (int i=0;i<numsSize;i++)

total += nums[i];

if (total== x)

return numsSize;

int left, right;

left=right=0;

int max = INT_MIN;

while (right < numsSize)

{

currSum += nums[right];

while (currSum >= (total - x) && left <= right)

{

if (currSum == (total - x))

{

if ((right - left +1) > max)

max = right - left +1;

}

currSum -= nums[left++];

}

right++;

}

return (max == INT_MIN)? (-1) : (numsSize-max);

}