跳转至

4067. 数对和受限的最长子数组

难度中等

题目描述

给你一个整数数组 nums。

如果不存在三个 互不相同 的下标 i、j 和 k，满足 l <= i, j, k <= r 且：

  • nums[i] + nums[j] == nums[k]

则子数组 nums[l..r] 是 有效 子数组。

返回 nums 中有效子数组的 最大 长度。

子数组 是数组中一个连续 非空 元素序列。

 

示例 1：

输入： nums = [2,3,5,3,2,1]

输出： 3

解释：

考虑子数组 [3, 5, 3]。由不同下标处的元素组成的数对，其元素和如下：

  • 3 + 5 = 8
  • 3 + 3 = 6，这里使用的是两个不同位置上的 3
  • 5 + 3 = 8

这些和都不等于剩余下标处的元素，因此该子数组是有效的。

每个长度为 4 的子数组都包含位于不同下标处的 2、3 和 5，并且 2 + 3 = 5。因此，不存在更长的有效子数组，答案为 3。

示例 2：

输入： nums = [3,4,5,6]

输出： 4

解释：

由不同下标处的任意两个元素相加，得到的和分别为 7、8、9、9、10 和 11。这些值都不等于剩余下标处的元素，因此整个数组都是有效的。

 

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 500

解法

方法一：双指针

思考

\(n\le 1000\)。对每个区间再枚举三个下标检查两数之和，端点已经是两层，里面再花平方时间就过不了。

一段里已经有 \(a+b=c\)，包含它的更长区间同样不合法，所以右端点右移时左端点只往右走。新进来的 \(x\) 破坏当前窗口，只有它等于窗口内某两数之和，或者等于某两数之差。

于是为窗口里每一对数维护和与绝对差的出现次数。 \(x\) 命中其中之一，就从左端删掉元素，并撤掉它参与的数对。每个数对只加入一次、删除一次。

窗口 \(\textit{nums}[l..r]\) 合法，当且仅当其中不存在三个互异下标，使两个位置上的元素之和等于第三个位置上的元素。一段不合法时，包含它的更长区间也不合法，因此右端点增大时左端点只增不减。

令 \(m=\max(\textit{nums})\)。 \(\textit{cntS}[s]\) 是当前窗口内元素和为 \(s\) 的数对个数， \(\textit{cntD}[d]\) 是绝对差为 \(d\) 的数对个数。和最大为 \(2m\)，差最大为 \(m\)。

右端点的值是 \(x\)，加入前窗口为 \([l,r)\)。 \(x\) 使窗口不合法，当且仅当其中已有两数之和为 \(x\)，或已有两数之差为 \(x\)。前者表示 \(x\) 是和，后者表示 \(x\) 是加数、另外两个元素都还在窗口里。元素都是正数，差用绝对值即可。

条件成立时取出左端元素 \(y\)，把 \(y\) 与仍留在 \([l,r)\) 中的每个元素组成的和、差从计数里减掉，直到窗口重新合法。然后再把 \(x\) 与 \([l,r)\) 中每个元素组成的和、差加进去，用 \(r-l+1\) 更新答案。

每个数对在较晚的端点进入时加入，在较早的端点离开时删除。时间复杂度 \(O(n^2)\)，空间复杂度 \(O(m)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maxSubarray(self, nums: List[int]) -> int:
        mx = max(nums)
        cnt_s = [0] * (mx << 1 | 1)
        cnt_d = [0] * (mx + 1)
        ans = l = 0

        for r, x in enumerate(nums):
            while cnt_s[x] > 0 or cnt_d[x] > 0:
                y = nums[l]
                l += 1
                for z in nums[l:r]:
                    cnt_s[y + z] -= 1
                    cnt_d[abs(y - z)] -= 1

            for y in nums[l:r]:
                cnt_s[x + y] += 1
                cnt_d[abs(x - y)] += 1

            ans = max(ans, r - l + 1)
        return ans

 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
class Solution {
    public int maxSubarray(int[] nums) {
        int mx = 0;
        for (int x : nums) {
            mx = Math.max(mx, x);
        }

        int[] cntS = new int[(mx << 1) | 1];
        int[] cntD = new int[mx + 1];
        int ans = 0;
        int l = 0;

        for (int r = 0; r < nums.length; r++) {
            int x = nums[r];
            while (cntS[x] > 0 || cntD[x] > 0) {
                int y = nums[l++];
                for (int i = l; i < r; i++) {
                    int z = nums[i];
                    cntS[y + z]--;
                    cntD[Math.abs(y - z)]--;
                }
            }

            for (int i = l; i < r; i++) {
                int y = nums[i];
                cntS[x + y]++;
                cntD[Math.abs(x - y)]++;
            }

            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

 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
class Solution {
public:
    int maxSubarray(vector<int>& nums) {
        int mx = ranges::max(nums);

        vector<int> cntS((mx << 1) | 1);
        vector<int> cntD(mx + 1);

        int ans = 0;
        int l = 0;

        for (int r = 0; r < nums.size(); r++) {
            int x = nums[r];

            while (cntS[x] > 0 || cntD[x] > 0) {
                int y = nums[l++];

                for (int i = l; i < r; i++) {
                    int z = nums[i];
                    cntS[y + z]--;
                    cntD[abs(y - z)]--;
                }
            }

            for (int i = l; i < r; i++) {
                int y = nums[i];
                cntS[x + y]++;
                cntD[abs(x - y)]++;
            }

            ans = max(ans, r - l + 1);
        }

        return ans;
    }
};

 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
func maxSubarray(nums []int) int {
    mx := slices.Max(nums)

    cntS := make([]int, (mx<<1)|1)
    cntD := make([]int, mx+1)

    ans := 0
    l := 0

    for r, x := range nums {
        for cntS[x] > 0 || cntD[x] > 0 {
            y := nums[l]
            l++

            for i := l; i < r; i++ {
                z := nums[i]
                cntS[y+z]--

                d := y - z
                if d < 0 {
                    d = -d
                }
                cntD[d]--
            }
        }

        for i := l; i < r; i++ {
            y := nums[i]
            cntS[x+y]++

            d := x - y
            if d < 0 {
                d = -d
            }
            cntD[d]++
        }

        ans = max(ans, r-l+1)
    }

    return ans
}

 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
function maxSubarray(nums: number[]): number {
    let mx = 0;
    for (const x of nums) {
        mx = Math.max(mx, x);
    }

    const cntS = new Array((mx << 1) | 1).fill(0);
    const cntD = new Array(mx + 1).fill(0);

    let ans = 0;
    let l = 0;

    for (let r = 0; r < nums.length; r++) {
        const x = nums[r];

        while (cntS[x] > 0 || cntD[x] > 0) {
            const y = nums[l++];
            for (let i = l; i < r; i++) {
                const z = nums[i];
                cntS[y + z]--;
                cntD[Math.abs(y - z)]--;
            }
        }

        for (let i = l; i < r; i++) {
            const y = nums[i];
            cntS[x + y]++;
            cntD[Math.abs(x - y)]++;
        }

        ans = Math.max(ans, r - l + 1);
    }

    return ans;
}

评论