TYS的博客

算法小白努力学习中

0%

区间和

发表于 更新于 分类于

leetcode 1477 找两个和为目标值且不重叠的子数组

leetcode 1658 将x减小到0的最小次数

leetcode 1423 可获得的最大点数

题目中给出的数据范围$1\le arr[i]\le10^4$，因此找到一段区间和为某一个数值，可以采用双指针的方式，如果当前区域的和大于target，则移动前面的指针，直到区间和小于等于target。如果存在负数或零，则采用前缀和与哈希表的方式。

对于题目1477 其要找到满足等于给定和的最小的两个不想交的区间，采用dp[j]表示区间右端点小于等于j的最小区间长度。
$$
dp[j] = \min(dp[j - 1], j - i + 1) \
ans = \min(ans, dp[i - 1] + j - 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
class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        int n = arr.size();
        int i = 0, sum = 0, ans = 0x3f3f3f3f;
        vector<int> dp(n, 0x3f3f3f3f);
        for (int j = 0; j < n; ++j) {
            sum += arr[j];
            while (sum > target && i < j) {
                sum -= arr[i];
                ++i;
            }
            if (j > 0) dp[j] = dp[j - 1];
            if (sum == target) {
                dp[j] = min(dp[j], j - i + 1);
                if (i > 0) {
                    ans = min(ans, dp[i - 1] + j - i + 1);
                }
            }
        }
        return ans == 0x3f3f3f3f ? -1 : ans;
    }
};

对于1658题，首先找到一段区间和为x，然后调整两个指针的位置使得两端区间和为x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int n = nums.size(), ans = 0x3f3f3f3f;
        int j = n - 1, sum = 0;
        while (j >= 0 && sum < x) {
            sum += nums[j];
            --j;
        }
        ++j;
        if (sum == x) ans = n - j;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            while (j < n && sum > x) {
                sum -= nums[j];
                ++j;
            }
            if (sum == x && j > i) {
                ans = min(ans, i + 1 + n - j);
            }
        }
        return ans == 0x3f3f3f3f ? -1 : ans;
    }
};