leetcode 560. 和为K的子数组 [php版本] 前缀和
首先是暴力解，挨个遍历子数组，然后依次查看和是否为K。很明显，无法AC.
然后是利用前缀和的方法，时间复杂度O(n^2),空间复杂度
function subarraySum($nums, $k) {
$preSum = [];
$preSum[0] = 0;
//presum[i] equal to nums[0...i-1]
for ($i = 0; $i < count($nums); $i++) {
$preSum[$i+1] = $preSum[$i] + $nums[$i];
}
$res = 0;
// for ($i = 1; $i<= count($nums); $i++) {
// for ($j = 0; $j< $i;$j++) {
// if ($preSum[$i] -$preSum[$j] == $k) {
// $res++;
// }
// }
// }
for ($i = 0; $i< count($nums); $i++) {
for ($j = $i; $j< count($nums);$j++) {
if ($preSum[$j+1] -$preSum[$i] == $k) {
$res++;
}
}
}
return $res;
}
最后一种是直接用hashmap存储一下出现过的前缀和,这里一开始看了别人的解释硬是没看明白，后来看了一个文章总算理解了。这里说一下吧，如果用preSum[i] 表示的是 nums[0….i] 的和， preSum[j] 表示的是 nums[0…j]的和， 那子数组nums[i:j]=(nums[0]+nums[1]+ ··· +nums[j]) – (nums[0]+nums[1]+ ··· +nums[i-1])=preSum[j]-preSum[i-1]，
我们可以用哈希表，我们可以在元素累加的过程中得到 preSum[j]=nums[0]+nums[1]+ ··· +nums[j]，并放入哈希表中。如果我们可以在哈希表中发现之前存在着 sum[i] 使得 preSum[j]-preSum[i]=k，那么也就说明了有一个子序列之和为 k。时间复杂度终于被降到了。之所以可以这么搞，是因为我们是从前往后依次遍历求和的。
现在时间复杂度是O(N)，可以AC了。
function subarraySum($nums, $k) {
$preSum = [];
$res = $sum0_i = 0;
$preSum[0] = 1;
for ($i = 0; $i < count($nums); $i++) {
$sum0_i += $nums[$i];
$sum0_j = $sum0_i - $k;
if (isset($preSum[$sum0_j])) {
$res += $preSum[$sum0_j];
}
$preSum[$sum0_i]++;
}
return $res;
}
ps:上面的方法再多说一句，比如一个数组nums:[5,2,4,1,3],现在sum0_i计算到了前四项的和 那么就可以查找hashmap 找缺少的和，比如前两项的和加上之后等于K，那么下标[1,3]的子数组就是满足条件的。
最后，再来个应用，求某个分数段的学生书
function preSumGrade($nums, $min, $max)
{
$score = [];
foreach ($nums as $grade) {
$score[$grade]++;
}
for ($i = 1; $i< 151; $i++) {
$score[$i] = $score[$i] + $score[$i-1];
}
// var_dump($score[91]-$score[60]);
var_dump($score);
return $score;
}