LeetCode-Array中几种连续子序列问题总结

LeetCode-Array中几种连续子序列问题总结

Posted by Jae on October 16, 2019

1 和能被K整除的子数组个数

1.1 题目

Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.

Example 1:

Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]


Note:

1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000


1.3 实现

public class Solution {
public int subarraysDivByK(int[] A, int K) {
int n = A.length;
int[] P = new int[n+1];
for (int i = 0; i < n; i++){
P[i+1] = P[i] + A[i];
}

int[] C = new int[K];
for (int x : P){
// 这里两次取模原因是java的取模可能返回负数
C[(x % K + K) % K]++;
}

int ans = 0;
for (int c : C){
ans += c * (c-1) / 2;
}
return ans;
}
}


2 连续子数组最大乘积

2.1 题目

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.


3 子数组累加和为K的个数

3.1 题目

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1: Input:nums = [1,1,1], k = 2 Output: 2 Note: The length of the array is in range [1, 20,000]. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

4 最小子数组和大于给定值

4.1 题目

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).


5 乘积小于K的连续子数组个数

5.1 题目

Your are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Example 1:

Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.


Note:

0 < nums.length <= 50000.
0 < nums[i] < 1000.
0 <= k < 10^6.
`