LeetCode 53 最大子序和

题目链接

链接：LeetCode链接

题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

解法

解法一：动态规划

  • 遍历数组，设sum[i]为以数组第i个元素结尾的连续子数组的和的最大值，记最后结果为result
  • 那么对于元素i，所有以它前面的元素结尾的子数组的最大和都已经求得，那么以第i个元素结尾且和最大的连续子数组，要么是以第i-1个元素结尾且和最大的连续子数组加上这个元素，要么是只包含第i个元素，即sum[i]= max(sum[i-1] + a[i], a[i])。
  • 可以通过判断sum[i-1] + a[i]是否大于a[i]来做选择，而这实际上等价于判断sum[i-1]是否大于0
  • 如果 sum[i-1] > 0，则说明 sum[i-1] 对当前结果有增益效果，则 sum 保留并加上当前遍历数值
  • 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
  • 每次比较 sum[i] 和 result 的大小，将最大值置为result，遍历结束返回结果
  • 由于每次运算只需要前一次的结果，因此并不需要像普通的动态规划那样保留之前所有的计算结果，只需要保留上一次的即可
  • 时间复杂度：O(n)

状态转移公式：
sum[i] = max(sum[i-1]+nums[i] , nums[i])
result = max(result,sum[i])

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maxSubArrayWithDP(int[] nums)
{
    if (nums == null || nums.length == 0)
    {
        return 0;
    }
    int result = nums[0];
    int sum = nums[0];
    for (int i = 1; i < nums.length; i++)
    {
        sum = Math.max(sum + nums[i], nums[i]); //(1)
        result = Math.max(result, sum);
    }
    return result;
}

注释中(1)处可以写为：

1
2
3
sum = (sum + nums[i] > nums[i]) ? sum + nums[i] : nums[i];
或者
sum = sum > 0 ? sum + nums[i] : nums[i];

解法二：分治法

将数组均分为两个部分，那么最大子数组会存在于

  • 左侧数组的最大子数组
  • 右侧数组的最大子数组
  • 左侧数组的以右侧边界为边界的最大子数组+右侧数组的以左侧边界为边界的最大子数组

参考：链接

子数组取值范围

题目描述

给定数组arr和整数num，共返回有多少个子数组如下情况：

  • max(arr[i..j]) - min(arr[i..j]) <= num
    • max(arr[i..j]) 表示子数组arr[i..j]中的最大值
    • min(arr[i..j]) 表示子数组arr[i..j]中的最小值

解法：双端队列

  • 如果一个子数组从L->R中，max(arr[i..j]) - min(arr[i..j]) <= num，那么在L->R范围内的子数组都符合要求
    • 我们以⼦数组 arr[i..j-1]为例说明, arr[i..j-1]最⼤值只可能⼩于或等于arr[i..j]的最大值, arr[i..j-1]最小值只可能大于或等于 arr[i..j]的最小值, 所以 arr[i..j-|]必然满⾜条件, 同理, arr[i..j]中的每⼀个⼦数组都满⾜条件　　
  • 如果⼦数组 arr[i..j]不满⾜条件, 那么所有包含 arr[i..j]的⼦数组, 即arrk..l都不满⾜条件

代码：

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
41
42
43
44
45
46
47
48
49
public int getNum(int[] array, int target)
{
    if (array == null || array.length == 0)
    {
        return 0;
    }
    int result = 0;
    LinkedList<Integer> minIndexQueue = new LinkedList<>();
    LinkedList<Integer> maxIndexQueue = new LinkedList<>();
    int i = 0;
    int j = 0;

    while (i < array.length)
    {
        while (j < array.length)
        {
            // 维护窗口最大值
            while (!maxIndexQueue.isEmpty() && array[maxIndexQueue.peekLast()] <= array[j])
            {
                maxIndexQueue.pollLast();
            }
            maxIndexQueue.addLast(j);

            // 维护窗口最小值
            while (!minIndexQueue.isEmpty() && array[minIndexQueue.peekLast()] >= array[j])
            {
                minIndexQueue.pollLast();
            }
            minIndexQueue.addLast(j);

            if (array[maxIndexQueue.getFirst()] - array[minIndexQueue.getFirst()] > target)
            {
                break;
            }
            j++;
        }
        if (minIndexQueue.peekFirst() == i)
        {
            minIndexQueue.pollFirst();
        }
        if (maxIndexQueue.peekFirst() == i)
        {
            maxIndexQueue.pollFirst();
        }
        result += j - i;
        i++;
    }
    return result;
}

LeetCode 560 和为K的子数组

题目链接

链接：LeetCode链接

题目描述

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

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

说明：
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]

解法

解法一：前缀和（截取法）

  • 在涉及连续子数组问题的时候，常常可以使用前缀和来解决它们。
    • 如线段 A..B..C，BC的长度 = AC的长度 - AB的长度
  • 那么在计算位于两个索引之间的元素之和时，我们可以减去对应于两个索引的累积和以直接获得总和。
  • 设sum[i]表示数组从序号0到i-1的元素的和，即sum[i] = A[0] + A[1] + … + A[i-1]
  • 则，子数组 nums [i:j] 的元素总和 = sum [j + 1] - sum [i]
  • 实际上也是动态规划
    • dp[i] = dp[i - 1] + nums[i - 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
public int subArraySumWithCache(int[] nums, int k)
{
    int result = 0;
    int[] sinceCurrentSumArray = new int[nums.length + 1];
    sinceCurrentSumArray[0] = 0;

    // 预处理，构造和
    for (int i = 1; i <= nums.length; i++)
    {
        sinceCurrentSumArray[i] = sinceCurrentSumArray[i - 1] + nums[i - 1];
    }

    for (int i = 0; i < nums.length; i++)
    {
        for (int j = i + 1; j <= nums.length; j++)
        {
            if (sinceCurrentSumArray[j] - sinceCurrentSumArray[i] == k)
            {
                result++;
            }
        }
    }
    return result;
}

解法二：Map查找

  • 基于以上截取法，设sum[i] = A[0] + A[1] + … + A[i-1]，则子数组 nums [i:j] 的元素总和 = sum [j + 1] - sum [i]
  • 则问题演变为，给定一个数组，是否存在两个元素的差 = K，如果存在，问这样的元素有多少对
  • 那么，我们构造这样的结构 (sum[i], sum[i]出现的次数) 的(key, value)对，当后面遍历的时候，只需搜索前面是否出现了 key = sum[j] - k 的元素对，累加对应的出现次数即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int subArraySumWithMap(int[] nums, int k)
{
    Map<Integer, Integer> map = new HashMap<>();
    // 初始化
    map.put(0, 1);
    int sum = 0;
    int result = 0;
    for (int i = 0; i < nums.length; i++)
    {
        sum += nums[i]; // 这里也可以与解法一结合，先用一个for循环用数组记录了所有sum，这里只顾搜索
        if (map.containsKey(sum - k))
        {
            result += map.get(sum - k);
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return result;
}

LeetCode 523 连续的子数组和

题目链接

链接：链接

题目描述

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

n 也是一个整数。
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
41
42
43
44

示例 1:
输入: [23,2,4,6,7], k = 6
输出: True
解释: [2,4] 是一个大小为 2 的子数组，并且和为 6。

示例 2:
输入: [23,2,6,4,7], k = 6
输出: True
解释: [23,2,6,4,7]是大小为 5 的子数组，并且和为 42。

说明:
数组的长度不会超过10,000。
你可以认为所有数字总和在 32 位有符号整数范围内。

## 解法 ##

### 解法一：前缀和（截取） ###
+ 设sum[i] = A[0] + A[1] + ... + A[i]，则nums[i..j]的和 = sum[j] - sum[i] + nums[i]（注意，与上题有一点不一样）
+ **注意，这里子数组的长度至少为2，在使用前缀和方法的时候，要注意sum数组的长度，是nums.length还是nums.length+1，对应双重for循环遍历的时候，i和j的边界取值问题。**
代码：
```java
public boolean checkSubArraySum(int[] nums, int k)
{
    int[] sum = new int[nums.length];
    sum[0] = 0;
    for (int i = 1; i < nums.length; i++)
    {
        sum[i] = sum[i - 1] + nums[i];
    }

    for (int i = 0; i < nums.length - 1; i++)
    {
        for (int j = i + 1; j < nums.length; j++)
        {
            int sumFromIToJ = sum[j] - sum[i] + nums[i];
            if (sumFromIToJ == k || ((k != 0) && (sumFromIToJ % k == 0)))
            {
                return true;
            }
        }
    }
    return false;
}

解法二：Map查找

  • 同样的，基于截取法，设j>i，要看是否存在sum[i..j] == nk，sum[i..j]可以看做sum[0..j] - sum[0..i]，即 sum[0..j] - sum[0..i] == nk
  • 到这里，可以想到map的key应该存放的是遍历到目前为止的sum，当遍历到j的时候，只需要看map中是否存在另一个元素的key使得sum[0..j] == sum[0..i] + nk，看到a=nk+b或者a=b-nk这种式子，就应该要想到同余定理，即 如果 a%b = c, 则有(a+kb)%b = c; (k为非0整数)，直接算不好算，那么可以把sum对k取余数，key存这个余数，当遍历到j时，就看map中是否存在其他元素的key与此时的key相同。（key为sum%k）
  • 采用逆推法，设遍历到i的时候和为sumi，假设存在和为nk的子数组，且以i为左端起始，j为右端结尾，那么遍历到j时的和位sumi + nk，根据同余定理，(sumi +nk) % k = sumi % k，如果key存的是截止到当前遍历位置的sum%k，以后就只需判断是否存在相同的key即可，因为存在相同的key时反过来推可以推出这一段子数组的和是nk
  • 由于还要判断子数组长度是否至少为2，因此value可以存数组index序号，value相减来判断是否满足长度至少为2
  • 同余定理在解题中有很大帮助
  • 采用map查找方法时，要注意初始化map

代码：

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
public boolean checkSubArraySumByMap(int[] nums, int k)
{
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);

    int sum = 0;
    for (int i = 0; i < nums.length; i++)
    {
        sum += nums[i];
        if (k != 0)
        {
            sum = sum % k;
        }
        if (map.containsKey(sum))
        {
            if (i - map.get(sum) > 1)
            {
                return true;
            }
        }
        else
        {
            map.put(sum, i);
        }
    }
    return false;
}

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

题目链接

链接：LeetCode链接

题目描述

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

示例：
输入：A = [4,5,0,-2,-3,1], K = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

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

解法

解法一：前缀和（截取法）

  • 时间复杂度O(N²)，空间复杂度O(N)，此题用该方法超时了

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int subArraysDivByK(int[] array, int k)
{
    int result = 0;
    int[] sinceCurrentSumArray = new int[array.length + 1];
    sinceCurrentSumArray[0] = 0;
    for (int i = 1; i <= array.length; i++)
    {
        sinceCurrentSumArray[i] = sinceCurrentSumArray[i - 1] + array[i - 1];
    }

    for (int i = 0; i < array.length; i++)
    {
        for (int j = i + 1; j <= array.length; j++)
        {
            if ((sinceCurrentSumArray[j] - sinceCurrentSumArray[i]) % k == 0)
            {
                result++;
            }
        }
    }
    return result;
}

解法二：Map查找法

  • 在方法一中我们利用前缀和数组来求解问题，对于子数组nums[i..j]，（不包含下标j)，其区间和为sum[j] - sum[i]，(其中sum为预处理得到的前缀和数组),
  • 我们要判断的是(sum[j]−sum[i])%K是否等于0。
    • 根据mod运算的性质，我们知道 (sum[j]−sum[i])%K = sum[j]%K−sum[i]%K。
    • 故若想(sum[j]−sum[i])%K=0，则必有 sum[j]%K = sum[i]%K。
    • 所有满足nums[i:j]中元素之和可以被K整除的开始下标i，必有sum[j]%K = sum[i]%K。我们以sum[i]%K作为键值统计其出现的频率，从而对于每个下标j我们可以立即获得能和它组成满足要求的子数组的开始下标i的数量。
  • 坑：由于数组中有可能出现负数，我们需要将其加KK从而使其%K之后的值为正数
  • 时间复杂度: O(N)，空间复杂度: O(K)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int subArraysDivByKWithMap(int[] array, int k)
{
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    int result = 0;
    int sum = 0;
    for (int i = 0; i < array.length; i++)
    {
        sum += array[i];
        int key = (sum % k + k) % k;
        if (map.containsKey(key))
        {
            result += map.get(key);
        }
        map.put(key, map.getOrDefault(key, 0) + 1);
    }
    return result;
}

LeetCode 713 乘积小于K的子数组

题目链接

链接：LeetCode链接

题目描述

给定一个正整数数组 nums。

找出该数组内乘积小于 k 的连续的子数组的个数。

示例 1:
输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。

说明:
0 < nums.length <= 50000
0 < nums[i] < 1000
0 <= k < 10^6

LeetCode 795 区间子数组个数

题目链接

链接：LeetCode链接

题目描述

给定一个元素都是正整数的数组A ，正整数 L 以及 R (L <= R)。
求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数。

例如 :
输入:
A = [2, 1, 4, 3]
L = 2
R = 3
输出: 3
解释: 满足条件的子数组: [2], [2, 1], [3].

注意:
L, R 和 A[i] 都是整数，范围在 [0, 10^9]。
数组 A 的长度范围在[1, 50000]。