文章目录
前缀和算法
剑指 Offer II 012. 左右两边子数组的和相等
剑指 Offer II 012. 左右两边子数组的和相等
给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
https://leetcode.cn/problems/tvdfij/
思路：
假如数组的所有和为 total，nums[i] 的和为 sum，那么右边的就是 total - sum - nums[i]，又因为 total - sum - nums[i] = sum，那么 total = 2*sum +nums[i]
。
class Solution {
public int pivotIndex(int[] nums) {
int total = Arrays.stream(nums).sum();
int sum = 0;
for (int i = 0; i < nums.length; ++i) {
if (2 * sum + nums[i] == total) {
return i;
}
sum += nums[i];
}
return -1;
}
}
- 时间：O(n)
- 空间：O(1)
剑指 Offer II 057. 值和下标之差都在给定的范围内
剑指 Offer II 057. 值和下标之差都在给定的范围内
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。
https://leetcode.cn/problems/7WqeDu/
思路：
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
// 特殊情况
if (nums.length < 2 || k == 0) return false;
// 保存长度为 k 的窗口内的数
TreeSet<Long> treeSet = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
// 由于 cur - floor 可能会出现溢出情况，所以用 Long 来表示
long cur = nums[i];
// 获取比 cur 小的数中最接近 cur 的数
Long floor = treeSet.floor(cur);
// 获取比 cur 大的数中最接近 cur 的数
Long ceiling = treeSet.ceiling(cur);
// 如果窗口中最接近 cur 的数 与 cur 的差 <= t, 说明存在这样的两个数，返回 true
if (floor != null && cur - floor <= t) return true;
if (ceiling != null && ceiling - cur <= t) return true;
// 将当前数添加到窗口中
treeSet.add(cur);
// 剔除窗口最左边的元素
if (i >= k) {
treeSet.remove(Long.valueOf(nums[i - k]));
}
}
return false;
}
}
- 时间：O(n*log(min(n,k)))
- 空间：O(min(n,k))
剑指 Offer II 009. 乘积小于 K 的子数组
剑指 Offer II 009. 乘积小于 K 的子数组
给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。
https://leetcode-cn.com/problems/ZVAVXX/
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (nums == null) {
return -1;
}
int len = nums.length;
if (len <= 0) {
return 0;
}
int left = 0;
int res = 0;
int product = 1;
//滑动窗口表示含义：滑动窗口表示以当前元素为结尾，且乘积 < k 的子数组
for (int right = 0; right < len; right++) {
// 如果当前元素大于 k，那么在其滑动窗口内就不存在子数组满足条件
if (nums[right] >= k) {
product = 1;
left = right + 1;
} else {
product *= nums[right];
while (product >= k) {
product /= nums[left];
left++;
}
// 见：https://leetcode-cn.com/problems/ZVAVXX/solution/c-jie-shi-xia-yuan-shu-mei-you-jie-shi-d-26kx/
res += right - left + 1;
}
}
return res;
}
}
- 时间：O(n)
- 空间：O(1)
剑指 Offer II 008. 和大于等于 target 的最短子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
https://leetcode-cn.com/problems/2VG8Kg/
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
int ans = Integer.MAX_VALUE;
int left = 0, right = 0;
int sum = 0;
while (right < len) {
sum += nums[right];
while (sum >= target) {
ans = Math.min(ans, right - left + 1);
sum -= nums[left];
left++;
}
right++;
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
- 双指针解法 时间 O(n) 空间O(1)
剑指 Offer II 010. 和为 k 的子数组
https://leetcode-cn.com/problems/QTMn0o/
首先计算数组各个位置的前缀和并保存在一个HashMap 中，然后使用各个位置的 前缀和减去 k，得出的结果如果在 hashMap 中存在，那么就说明存在这样的一个子数组。
// 1.枚举实现
class Solution {
public int subarraySum(int[] nums, int k) {
if (nums == null) {
return 0;
}
int res = 0;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if (sum == k) {
res++;
}
}
}
return res;
}
}
// 2.前缀和 实现
class Solution02 {
public int subarraySum(int[] nums, int k) {
if (nums == null) {
return 0;
}
int res = 0;
HashMap<Integer, Integer> mp = new HashMap<>();
mp.put(0, 1);
int pre = 0;
for (int i = 0; i < nums.length; i++) {
// 求真实的前缀和
pre += nums[i];
//
if (mp.containsKey(pre - k)) {
res += mp.get(pre - k);
}
mp.put(pre, mp.getOrDefault(pre, 0) + 1);
}
return res;
}
}
- 时间：O(n)
- 空间：O(n)
最长重复子数组
https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
思路1：DP
// 动态规划
class Solution {
public int findLength(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) {
return 0;
}
int len1 = nums1.length;
int len2 = nums2.length;
int[][] dp = new int[len1 + 1][len2 + 1];
int res = -1;
for (int i = len1 - 1; i >= 0; i--) {
for (int j = len2 - 1; j >= 0; j--) {
if (nums1[i] == nums2[j]) {
// 这里的DP方程，我真的是 没理解。。。。
dp[i][j] = dp[i + 1][j + 1] + 1;
} else {
dp[i][j] = 0;
}
res = Math.max(res, dp[i][j]);
}
}
return res;
}
}
- 时间：O(m*n)
- 空间：O(m*n)
思路2：滑动窗口（具体思路见题解）
class Solution02 {
public int findLength(int[] A, int[] B) {
int n = A.length, m = B.length;
int ret = 0;
// 数组 B 不动, A 动
for (int i = 0; i < n; i++) {
int len = Math.min(m, n - i);
int maxlen = maxLength(A, B, i, 0, len);
ret = Math.max(ret, maxlen);
}
// 数组 A 不动, B 动
for (int i = 0; i < m; i++) {
int len = Math.min(n, m - i);
int maxlen = maxLength(A, B, 0, i, len);
ret = Math.max(ret, maxlen);
}
return ret;
}
// 求长度 len 中最长相等的长度
public int maxLength(int[] A, int[] B, int addA, int addB, int len) {
int ret = 0, k = 0;
for (int i = 0; i < len; i++) {
if (A[addA + i] == B[addB + i]) {
k++;
} else {
k = 0;
}
ret = Math.max(ret, k);
}
return ret;
}
}
- 时间：O(（m+n）*min（m,n）)
- 空间：O(1)
11. 盛最多水的容器
https://leetcode-cn.com/problems/container-with-most-water/
思路：双指针O(n) 解法
初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。
// 2. O(n) 双指针 解法
class Solution02 {
public int maxArea(int[] height) {
if (height == null) {
return 0;
}
int res = 0;
int left = 0;
int right = height.length - 1;
while (left < right) {
res = Math.max(res, Math.min(height[left], height[right]) * (right - left));
// 向内移动 较短边
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return res;
}
}