前缀和系列

评论

前缀和

前缀和，简单说就是数组的前 n 项的和。不过需要注意，在代码里面，presum[i] 代表前 i 项的和，也就是 nums[0]~nums[i-1]的和。
比如 presum[2] = nums[0] + nums[1]。

通过前缀和的思想和 map，可以优化很多问题解法。

同时前缀和不一定真的就是前缀的和，也可以是前缀中奇数数字的个数等。总之就前缀的一个统计信息，可以是和，也可以是其他。

1
2
3
4
5
6
function presum(nums: number): number[] {
  let presum = [0];
  for (let i = 0; i < nums.length; i++) {
    presum[i + 1] = presum[i] + nums[i];
  }
}

724. 寻找数组的中心下标

给你一个整数数组  nums，请编写一个能够返回数组 “中心下标” 的方法。数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。如果数组不存在中心下标，返回 -1 。如果数组有多个中心下标，应该返回最靠近左边的那一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 先求出总和
// 遍历求出左边的和，然后用总和减去左边的和以及当前值，就是右边的和
// 判断左右的和是否相等
function pivotIndex(nums: number[]): number {
  let presum = 0;
  for (let i = 0; i < nums.length; i++) {
    presum += nums[i];
  }

  let leftsum = 0;
  let rightsum = 0;
  for (let i = 0; i < nums.length; i++) {
    rightsum = presum - leftsum - nums[i];
    if (leftsum === rightsum) {
      return i;
    }
    leftsum += nums[i];
  }
  return -1;
}

1. 两数之和

给定一个整数数组 nums  和一个整数目标值 target，请你在该数组中找出 和为目标值 的那   两个   整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 使用一个map，记录已经访问过的值
// 遍历数组，判断map中是否已经存在一个值，和当前值相加的和是target
// 如果不是，就把当前值加入到map中
function twoSum(nums: number[], target: number): number[] {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (map.has(target - nums[i])) {
      return [map.get(target - nums[i]), i];
    }
    map.set(nums[i], i);
  }
  return [];
}

560. 和为 K 的子数组

给定一个整数数组和一个整数  k，你需要找到该数组中和为  k  的连续的子数组的个数。

示例 1 : 输入:nums = [1,1,1], k = 2; 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 暴力法，求出了所有子数组的和
// 有可能会超时
function subarraySum(nums: number[], k: number): number {
  let sum = 0;
  let cnt = 0;
  for (let i = 0; i < nums.length; i++) {
    sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      if (sum === k) {
        cnt++;
      }
    }
  }
  return cnt;
}

// 与两数之和类似，使用map节省时间
// map 中记录前缀和，以及该前缀和出现的次数
function subarraySum(nums: number[], k: number): number {
  let presum = 0;
  let cnt = 0;
  const map = new Map();
  map.set(0, 1);
  for (let i = 0; i < nums.length; i++) {
    presum += nums[i];
    if (map.has(presum - k)) {
      cnt += map.get(presum - k);
    }
    const curVal = map.has(presum) ? map.get(presum) : 0;
    map.set(presum, curVal + 1);
  }
  return cnt;
}

1248. 统计优美子数组

给你一个整数数组  nums 和一个整数 k。如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。请返回这个数组中「优美子数组」的数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 使用位运算判断数字的奇偶性
function isOdd(num: number): boolean {
  return (num & 1) === 1;
}

// 暴力法，遍历所有的子数组，计算子数组奇数的个数，判断个数是否为k
function numberOfSubarrays(nums: number[], k: number): number {
  let cnt = 0;
  let oddCnt = 0;
  for (let i = 0; i < nums.length; i++) {
    oddCnt = 0;
    for (let j = i; j < nums.length; j++) {
      if (isOdd(nums[j])) oddCnt++;
      if (oddCnt === k) cnt++;
    }
  }
  return cnt;
}

// presum 记录的是当前前缀中的奇数的个数
// map记录前缀中奇数个数，以及该种case出现的次数
// 比如map(5,2) 代表，该前缀中有5个奇数，它出现了2次
function numberOfSubarrays(nums: number[], k: number): number {
  let cnt = 0;
  let presum = 0;
  const map = new Map();
  map.set(0, 1);

  for (let i = 0; i < nums.length; i++) {
    presum += isOdd(nums[i]) ? 1 : 0;
    if (map.has(presum - k)) {
      cnt += map.get(presum - k);
    }
    const curVal = map.has(presum) ? map.get(presum) : 0;
    map.set(presum, curVal + 1);
  }
  return cnt;
}

974. 和可被 K 整除的子数组

给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。

  • 这里的 k 大于 2
  • 数组 A 中有负数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 暴力法
// 求出所有子数组的和，验证是否可以被K整除
// 超时了
function subarraysDivByK(A: number[], K: number): number {
  let cnt = 0;
  let sum = 0;
  for (let i = 0; i < A.length; i++) {
    sum = 0;
    for (let j = i; j < A.length; j++) {
      sum += A[j];
      if (sum % K === 0) {
        cnt++;
      }
    }
  }
  return cnt;
}

// presum 还是前缀和
// map记录前缀和对K的余数，以及次数
// (presum[i]-presum[j]) % K = 0 --> presum[i] % K = presum[j] % K
function subarraysDivByK(A: number[], K: number): number {
  let cnt = 0;
  let presum = 0;
  let remainder = 0; // 余数
  const map = new Map();
  // map记录前缀和对K的余数，以及次数
  map.set(0, 1);
  for (let i = 0; i < A.length; i++) {
    presum += A[i];
    // 这里需要把负数的余数转成正数
    remainder = ((presum % K) + K) % K;
    if (map.has(remainder)) {
      cnt += map.get(remainder);
    }
    const curVal = map.has(remainder) ? map.get(remainder) : 0;
    map.set(remainder, curVal + 1);
  }
  return cnt;
}

523. 连续的子数组和

给定一个包含 非负数 的数组和一个目标 整数  k ，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n * k ，其中 n 也是一个整数。

  • k 是整数，可能为 0
  • 子数组长度至少为 2
  • 返回 bool 值，判断这个值是否存在
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// map的key为余数，val不再是余数出现的次数，而是该余数最早出现的位置
// 通过这个位置来判断，子树组长度是否大于等于2
// k为0的时候，余数就是presum本身，也就变成了是否有两个前缀和是相等的。
function checkSubarraySum(nums: number[], k: number): boolean {
  let presum = 0;
  let remainder = 0;
  const map = new Map();
  map.set(0, -1);
  for (let i = 0; i < nums.length; i++) {
    presum += nums[i];
    remainder = k === 0 ? presum : ((presum % k) + k) % k;
    if (map.has(remainder)) {
      const index = map.get(remainder);
      if (i - index >= 2) {
        return true;
      }
    } else {
      map.set(remainder, i);
    }
  }
  return false;
}

930. 和相同的二元子数组