算法复杂度优化的技巧

一、移项法

●原理： 所谓的移项法，就是将目标等式进行左右等价变化，辅助以哈希表/桶，从而减少类似for(j:for(i))的双层循环

●效果： 将算法从 $ O(n^2) $ 复杂度降低为 $ O(n) $

1590.使数组和能被P整除

前置余数知识

1、( a + b ) % p = a % p + b % p

2、假如( x - y) % p == 0 1. 假设x >= 0,y >= 0, 则有 x % p == y % p 2. 假设上面的某一方x < 0，则有x % p + p == y % p

思路

1、利用余数结论，计算前缀和对p的余数，则 s[n]就表示整体sum对p的余数。

2、则问题等价于找到 - 2.1、在前缀和数组上找到两个数 s[left]和 s[right]，满足 right−left最小且(s[right]−s[left]) % p == s[n] - 2.2、移项，s[right]−s[n] % p == s[left] - 2.3、考虑可能出现正负((s[right] − s[n]) % p + p) % p = s[left]

3、 避免双层遍历找left和right：使用一个哈希，存储s[i]出现的最近下标

4、遍历一遍，到了right，就找哈希里面是否存在left满足 = ((s[right] − s[n]) % p + p) % p

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int minSubarray(vector<int> &nums, int p)
{
    int n = nums.size(), ans = n, s[n + 1];
    s[0] = 0;
    for (int i = 0; i < n; ++i)
        s[i + 1] = (s[i] + nums[i]) % p;
    int x = s[n];
    if (x == 0)
        return 0; // 移除空子数组（这行可以不要）

    unordered_map<int, int> last;
    for (int i = 0; i <= n; ++i)
    {
        last[s[i]] = i;
        auto it = last.find((s[i] - x + p) % p);
        if (it != last.end())
            ans = min(ans, i - it->second);
    }
    return ans < n ? ans : -1;
}

面试题 17.05. 字母与数字

思路

1、前缀计数：left1[i]记录到i位置的字母个数，left2[j]记录到j位置的数字个数

2、思路1：暴力，$ O(n^2) $ ，看看什么位置满足left1[j]-left1[i] == left2[j]-left2[i],找到最小的i

3、思路2：移项，$ O(n) $ ，即找到left1[j]-left2[j] == left1[i]-left2[i]，那么用map保存当前差值(left1[i]-left2[i])出现的最早位置

当然这题对字母、数字建模为-1，1。可以压缩空间到O(n); 且用桶代替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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
vector<string> findLongestSubarray(vector<string> &array)
{
    unordered_map<int, int> uii;
    vector<int> left1(array.size() + 1, 0);
    vector<int> left2(array.size() + 1, 0);

    vector<string> ansv;
    int ans = 0;
    pair<int, int> ansp = make_pair(array.size() + 1, array.size() + 1);
    for (int i = 0; i < array.size(); i++)
    {
        if ((array[i][0] >= 'A' && array[i][0] <= 'Z') || (array[i][0] >= 'a' && array[i][0] <= 'z'))
        {
            left1[i + 1] = left1[i] + 1;
            left2[i + 1] = left2[i];
        }
        else
        {
            left1[i + 1] = left1[i];
            left2[i + 1] = left2[i] + 1;
        }
    }
    for (int j = 0; j <= array.size(); j++)
    {
        int tp = left1[j] - left2[j];
        if (uii.find(tp) != uii.end())
        {
            if (j - uii[tp] + 1 > ans)
            {
                ansp.first = uii[tp];
                ansp.second = j;
                ans = max(ans, j - uii[tp] + 1);
            }
            else if (j - uii[tp] + 1 == ans && uii[tp] < ansp.first)
            {
                ansp.first = uii[tp];
                ansp.second = j;
            }
        }
        else
        {
            uii[tp] = j;
        }
    }
    if (ansp.first == array.size() + 1)
        return ansv;
    for (int i = ansp.first; i < ansp.second; i++)
    {
        ansv.push_back(array[i]);
        cout << array[i] << " ";
    }
    return ansv;
}

2488. 统计中位数为 K 的子数组

思路1

0、找到k所在的位置kInd

1、写出目标表达式：: 

1
2
3
4
5
6
7
8
9
10
// 对于奇数长度的子序列：
「左侧小于 + 右侧小于 = 左侧大于 + 右侧大于」
//等价于
「左侧小于 - 左侧大于 = 右侧大于 - 右侧小于」

// 对于偶数长度的子序列：
「左侧小于 + 右侧小于 + 1 = 左侧大于 + 右侧大于」
//等价于
「左侧小于 - 左侧大于 = 右侧大于 - 右侧小于 - 1」

2、统计kInd左右侧，每个位置到kInd这段子数组中，小于、大于K值的位置数，分别记为smallK、bigK；

3、用一个哈希记录左侧每个位置的smallK - bigK位置数、右侧bigK-smallK的位置数，然后同时开第2个维度，记录位置的距离kInd的奇、偶。

4、之后根据不同位置距离kInd的奇数、偶数，可以得到子序列的奇偶，也就可以使用步骤1中的目标表达式，具体见下面代码

思路2：

参考：灵神的神级建模，见原题解

代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// （思路1）
int countSubarrays(vector<int> &nums, int k)
{
    int ans = 0;
    int kInd = -1;
    int bigK;
    int smallK;
    unordered_map<int, vector<int>> leftH;
    unordered_map<int, vector<int>> rightH;

    set<int> hasPos;

    for (int i = 0; i < nums.size(); i++)
        if (nums[i] == k)
            kInd = i;
    int i = kInd - 1, j = kInd + 1;

    leftH[0] = {1, 0};
    rightH[0] = {1, 0};
    smallK = 0;
    bigK = 0;
    hasPos.insert(0);
    // 统计
    while (i >= 0)
    {
        if (nums[i] < k)
        {
            smallK++;
        }
        else
        {
            bigK++;
        }
        if (leftH.find(smallK - bigK) == leftH.end())
        {
            vector<int> tp = {0, 0};
            tp[(kInd - i) % 2] = 1;
            leftH[smallK - bigK] = tp;
        }
        else
        {
            leftH[smallK - bigK][(kInd - i) % 2]++;
        }
        i--;
    }
    smallK = 0;
    bigK = 0;
    while (j < nums.size())
    {

        if (nums[j] < k)
        {
            smallK++;
        }
        else
        {
            bigK++;
        }

        if (rightH.find(bigK - smallK) == rightH.end())
        {
            vector<int> tp = {0, 0};
            tp[(j - kInd) % 2] = 1;
            rightH[bigK - smallK] = tp;
        }
        else
        {
            rightH[bigK - smallK][(j - kInd) % 2]++;
        }
        hasPos.insert(bigK - smallK);
        j++;
    }

    // hash统计位置数
    for (auto pos : hasPos)
    {
        if (leftH.find(pos) != leftH.end())
        {
            int rOu = rightH[pos][0];
            int lOu = leftH[pos][0];
            int rJi = rightH[pos][1];
            int lJi = leftH[pos][1];
            ans += rOu * lOu;
            ans += rJi * lJi;
        }
        if (leftH.find(pos - 1) != leftH.end())
        {
            ans += rightH[pos][0] * leftH[pos - 1][1];
            ans += rightH[pos][1] * leftH[pos - 1][0];
        }
    }
    return ans;
}

二、剪枝

●原理： 广义的剪枝法，就是将没有必要的搜索空间直接跳过，常见于递归问题。但要建立一个剪枝的思想，在各类问题中都适用，不局限于递归、搜索树。

●效果： 将算法进行不同程度优化

1615. 最大网络秩

参考(关注思路2的分类讨论)：leetcode官方题解

基础算法
#leetcode
算法复杂度优化的技巧
https://al-377.github.io/2023/09/17/algorithm-complex-optim/
作者
Aidan Lew
发布于
2023年9月17日
许可协议