想要精通算法和SQL的成长之路 - 连续的子数组和

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 连续的子数组和

原题链接

1.1 最原始的前缀和

如果这道题目，用前缀和来算，我们的思路一般是这样：

1. 计算这个数组的前缀和。
2. 循环遍历数组的每个元素，以每个元素作为起点，向后寻找第二个元素（索引至少是起点+2）作为终点，计算两者的区域和。再判断是否满足条件。

那么这样的代码写出来就是这样：

public boolean checkSubarraySum(int[] nums, int k) {int n = nums.length;// 计算前缀和int[] preSum = new int[n + 1];for (int i = 0; i < n; i++) {preSum[i + 1] = preSum[i] + nums[i];}// i 遍历到 preSum。length -2 即可，for (int i = 0; i < n - 1; i++) {// 区间长度 > 2for (int j = i + 2; j <= n; j++) {// 前缀和差即是[i,j]之间的区域和int diff = preSum[j] - preSum[i];if (diff % k == 0) {return true;}}}return false;
}

结果如下：

1.2 前缀和 + 哈希表

我们从这段代码入手：

int diff = preSum[j] - preSum[i];
if (diff % k == 0) {return true;
}

即:

• (preSum[j] - preSum[i] ) % k = 0;
• preSum[j] % k == preSum[i] % k;

那么我们只需要利用哈希表，记录每个前缀和对于k的一个取模值是多少即可，1. 存储的是它们的下标。
2. 如果遇到取模值相同的，并且两个下标差 > 2，就满足条件。

那么代码优化：

public boolean checkSubarraySum(int[] nums, int k) {int n = nums.length;// 计算前缀和int[] preSum = new int[n + 1];for (int i = 0; i < n; i++) {preSum[i + 1] = preSum[i] + nums[i];}HashSet<Integer> set = new HashSet<>();for (int i = 2; i <= n; i++) {set.add(preSum[i - 2] % k);if (set.contains(preSum[i] % k)) {return true;}}return false;
}