[1508] Range Sum of Sorted Subarray Sums

原來用暴力解下去做就好了嗎？！（沉思）

那我為什麼要看solution 裡面超難懂的最多有四種解法的有口皆悲人的解釋呢Orz

說是一個counting sort

奇怪是我變笨了還是counting sort 真的寫下去會有點卡住Orz (只有你吧QQ)

int rangeSum(int* nums, int numsSize, int n, int left, int right) {

int sum=0;

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

sum+=nums[i];

int *countSum = calloc(sum+1, sizeof(int));

int sub;

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

{

sub = 0;

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

{

sub+=nums[j];

countSum[sub]++;

}

}

for (int i=1; i<sum+1; i++)//change it from count to current count sum

countSum[i]+=countSum[i-1];

int ret = 0;

int LR = 1;

for (int i=1; i<sum+1; i++)

{

while (LR <= countSum[i])

{

if (LR>= left && LR<=right)

{

ret += i;

if (ret > 100000000)

ret = ret %1000000007;

}

LR++;

}

if (LR > right)

break;

}

return ret;

}

#if 0

1,2,3 => 1,2,2,2,3,3,3,3,3

[1,3,5]

[1,4,9]

#endif

來看看qsort ?! 哦原來qsort 真的慢了很多(thinking 圖)

int comp(const void *a, const void *b)

{

return (*(int*)a-*(int*)b);

}

int rangeSum(int* nums, int numsSize, int n, int left, int right) {

int len = (1+numsSize)*(numsSize)/2;

int *countSum = calloc(len, sizeof(int));

int sub;

int idx=0;

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

{

sub = 0;

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

{

sub+=nums[j];

countSum[idx++]=sub;

}

}

qsort (countSum,len, sizeof(int),comp);

int ret = 0;

for (int i=left-1; i<right; i++)

{

ret += countSum[i];

if (ret > 100000000)

ret = ret %1000000007;

}

return ret;

}