Monthly Archives: August 2020

剑指 Offer 11. 旋转数组的最小数字

剑指 Offer 11. 旋转数组的最小数字剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。  

示例 1:

输入:[3,4,5,1,2]
输出:1
示例 2:

输入:[2,2,2,0,1]
输出:0
注意:本题与主站 154 题相同:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。剑指 Offer 11. 旋转数组的最小数字


LeetCode Find Minimum in Rotated Sorted Array II相同,即旋转有序数组中包含重复元素,求最小值。考虑nums[m]==nums[r]的情况,退化为线性查找,完整代码如下:

class Solution {
public:
	int minArray(vector<int>& numbers) {
		int n = numbers.size();
		int l = 0, r = n - 1;
        while(l <= r) {
            if(r - l <= 1) return min(numbers[l], numbers[r]);
            int m = l + (r - l) / 2;
            if(numbers[m] > numbers[r]) l = m;
            else if(numbers[m] == numbers[r]) --r;
            else r = m;
        }
		return 0;
	}
};

本代码提交AC,用时12MS。

剑指 Offer 10- II. 青蛙跳台阶问题

剑指 Offer 10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:2
示例 2:

输入:n = 7
输出:21
示例 3:

输入:n = 0
输出:1
提示:

0 <= n <= 100
注意:本题与主站 70 题相同:https://leetcode-cn.com/problems/climbing-stairs/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


对于跳到第n的位置,有两种来源,如果这一跳是2步,则f(n)=f(n-2),如果这一跳是1步,则f(n)=f(n-1),所以总的情况是f(n)=f(n-2)+f(n-1),也就是求斐波那契数列的第n项。

完整代码如下:

class Solution {
public:
    int numWays(int n) {
        if(n == 0) return 1;
        if(n == 1) return 1;
        if(n == 2) return 2;
        int a = 1, b = 2;
        for(int i = 3; i <= n; ++i) {
            int tmp = (a + b) % 1000000007;
            a = b;
            b = tmp;
        }
        return b;
    }
};

本代码提交AC,用时0MS。

LeetCode K Closest Points to Origin

973. K Closest Points to Origin

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)

Note:

  1. 1 <= K <= points.length <= 10000
  2. -10000 < points[i][0] < 10000
  3. -10000 < points[i][1] < 10000

给定二维平面上的若干个点,求距离原点最近的K个点。

看总结: https://leetcode-cn.com/problems/k-closest-points-to-origin/solution/cyu-yan-san-chong-jie-fa-han-zong-jie-by-gan-cui-j/

事实上,诸如此类的,要在一个数组中寻找第K大的数(或者第K小的数),前K大的数,前K小的数,一般来说的方法有:

1.先排序(快排)时间复杂度为nlogn
2.建堆,堆的大小为K,建立大根堆或者小根堆,时间复杂度为nlogK(如果要求出前K个较大的,那么就建立小根堆,一旦比堆顶大,那么就入堆);
3.结合快速排序划分的方法,不断减小问题的规模

对于这一题,采用解法3,即快排划分的思路。采用标准快排思路,每次选区间最右边的元素作为pivot,然后划分,看看划分后的pivot位置和K的大小关系,递归在左右区间进行划分。完整代码如下:

class Solution {
private:
	vector<int> origin;

	int CalDist(vector<int> &p1, vector<int> &p2) {
		return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
	}

	void MySwap(vector<vector<int>>& points, int u, int v) {
		swap(points[u][0], points[v][0]);
		swap(points[u][1], points[v][1]);
	}

	void Work(vector<vector<int>>& points, int l, int r, int K) {
		if (l >= r) return;

		int pivot = r;
		int pdist = CalDist(points[pivot], origin);
		int i = l;
		for (int j = l; j < r; ++j) {
			int idist = CalDist(points[j], origin);
			if (idist < pdist) {
				MySwap(points, i++, j);
			}
		}
		MySwap(points, i, pivot);

		if (K == i)return;
		else if (K < i)Work(points, l, i - 1, K);
		else Work(points, i + 1, r, K);
	}
public:
	vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
		origin = { 0, 0 }; // 求与该点距离最近的top-k个点,本题中该点是原点

		for (int i = 0; i < points.size(); ++i) {
			printf("x=%d,y=%d,dist=%d\n", points[i][0], points[i][1], CalDist(points[i], origin));
		}

		Work(points, 0, points.size() - 1, K - 1);

		vector<vector<int>> ans;
		for (int i = 0; i < K; ++i) ans.push_back(points[i]);
		return ans;
	}
};

本代码提交AC,用时612MS。

HDOJ 1007-Quoit Design

HDOJ 1007-Quoit Design

Quoit Design

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 77740    Accepted Submission(s): 20729

Problem DescriptionHave you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.
In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.

Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.

InputThe input consists of several test cases. For each case, the first line contains an integer N (2 <= N <= 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0.

OutputFor each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 decimal places.

Sample Input

2
0 0
1 1
2
1 1
1 1
3
-1.5 0
0 0
0 1.5
0

Sample Output

0.71
0.00
0.75

AuthorCHEN, Yue 
SourceZJCPC2004
RecommendJGShining   |   We have carefully selected several similar problems for you:  10061009100510081004


给定二维平面上的N个点,问其中距离最近的两个点的距离是多少,输出最短距离的一半。

典型的平面上最近点对问题。大学算法课上有,采用分治法。即首先把所有点按x排序,然后取x轴中点m,把所有点划分为左右两半L和R,在L和R中递归求最近点对的距离,假设为dL和dR。假设d=min(dL,dR)。则还需要判断最近点对是否会在中点m附近,假设存在这种情况,则跨越m的最近点对必须满足距离m小于d。把这部分点收集起来,按y排序,然后求任意两点之间的距离,期间可以break加速。

完整代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;

struct Point
{
	double x_, y_;
	Point() :x_(0), y_(0) {};
	Point(double x, double y) :x_(x), y_(y) {};
};

bool CmpX(const Point &p1, const Point &p2) {
	return p1.x_ < p2.x_;
}

bool CmpY(const Point &p1, const Point &p2) {
	return p1.y_ < p2.y_;
}

// 暂时只算距离平方,最后开平方根
double CalDist(const Point &p1, const Point &p2) {
	return (p1.x_ - p2.x_)*(p1.x_ - p2.x_) + (p1.y_ - p2.y_)*(p1.y_ - p2.y_);
}

double CalMinDist(vector<Point> &data, int l, int r) {

	if (r - l == 2) {
		return CalDist(data[l], data[l + 1]);
	}
	else if (r - l == 3) {
		double d1 = CalDist(data[l], data[l + 1]);
		double d2 = CalDist(data[l], data[l + 2]);
		double d3 = CalDist(data[l + 1], data[l + 2]);
		return min(min(d1, d2), d3);
	}

	int m = l + (r - l) / 2;
	int mx = data[m].x_;
	double dd = min(CalMinDist(data, l, m), CalMinDist(data, m, r));
	double d = sqrt(dd);

	vector<Point> rect;
	for (int i = l; i < r; ++i) {
		if (data[i].x_ > mx - d && data[i].x_ < mx + d) {
			rect.push_back(data[i]);
		}
	}

	sort(rect.begin(), rect.end(), CmpY);
	for (int i = 0; i < rect.size(); ++i) {
		for (int j = i + 1; j < rect.size(); ++j) {
			double tmpd = CalDist(rect[i], rect[j]);
			if (tmpd > dd)break;
			dd = min(dd, tmpd);
		}
	}

	return dd;
}

int main() {
	freopen("input.txt", "r", stdin);

	int n;
	while (scanf("%d", &n)) {
		if (n == 0)break;
		vector<Point> data(n, Point());
		for (int i = 0; i < n; ++i) {
			scanf("%lf %lf", &data[i].x_, &data[i].y_);
		}
		sort(data.begin(), data.end(), CmpX);
		printf("%.2lf\n", sqrt(CalMinDist(data, 0, data.size())) / 2);
	}

	return 0;
}

本代码提交AC,用时982MS。

参考: https://www.cnblogs.com/MartinLwx/p/9757828.htmlhttps://www.jianshu.com/p/8bc681afbaff

剑指 Offer 10- I. 斐波那契数列

剑指 Offer 10- I. 斐波那契数列

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:

F(0) = 0,   F(1) = 1
F(N) = F(N – 1) + F(N – 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:1
示例 2:

输入:n = 5
输出:5
 

提示:

0 <= n <= 100
注意:本题与主站 509 题相同:https://leetcode-cn.com/problems/fibonacci-number/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


求斐波那契数列的第n项。看之前的POJ题解: http://code.bitjoy.net/2017/05/04/poj-3070-fibonacci/

一共有三种解法。常规解法就是无脑递归调用。关键是如何分析这种解法的时空复杂度。无脑调用是F(n)=F(n-1)+F(n-2)。想象一下,递归调用二叉树( https://wmjtxt.github.io/2018/12/26/three_method_of_fibonacci/ )。每个节点都会分裂出2个孩子,然后孩子继续2倍分裂,所以总调用次数大概是$O(2^n)$,这是时间复杂度。空间复杂度就是递归调用的栈深度,就是树的高度,大概是$O(n)$。

常规解法是,DP的思路,每次保留数列前两项,然后不断更新这两个数。时间复杂度是$O(n)$,空间复杂度是O(1)。完整代码如下:

class Solution {
public:
    int fib(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        long long a = 0, b = 1;
        for(int i = 2; i <= n; ++i) {
            long long tmp = a + b;
            tmp %= 1000000007;
            a = b;
            b = tmp;
        }
        return b;
    }
};

本代码提交AC,用时0MS。

最优的解法是矩阵快速幂的方法,求矩阵[[1,1],[1,0]]的n次幂,然后矩阵逆对角线位置的值就是F(n)的值。快速幂可以做到$O(lg(n))$的时间复杂度,完整代码如下:

typedef long long LL;

class Solution {
private:
    vector<vector<LL>> multiply(vector<vector<LL>> &m1, vector<vector<LL>> &m2) {
        int n = m1.size();
        vector<vector<LL>> ans(n, vector<LL>(n, 0));
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                for(int k = 0; k < n; ++k) {
                    ans[i][j] += m1[i][k] * m2[k][j] % 1000000007;
                }
            }
        }
        return ans;
    }
public:
    int fib(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;

        vector<vector<LL>> matrix = {{1,1},{1,0}};

        vector<vector<LL>> ans = {{1,0},{0,1}};
        while(n != 0) {
            if(n % 2 == 1) ans = multiply(ans, matrix);
            matrix = multiply(matrix, matrix);
            n >>= 1;
        }

        return ans[0][1] % 1000000007;
    }
};

本代码提交AC,用时4MS。

剑指 Offer 09. 用两个栈实现队列

剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

示例 1:

输入:
[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[3],[],[]]
输出:[null,null,3,-1]
示例 2:

输入:
[“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[],[5],[2],[],[]]
输出:[null,-1,null,null,5,2]
提示:

1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


用两个栈实现一个队列。栈是后进先出,队列是先进先出。设置两个栈stack_in_和stack_out_,分别负责数据的push和pop,如果stack_out_没数据,则需要从stack_in_中把数据捣腾到stack_out_中。完整代码如下:

class CQueue {
private:
    stack<int> stk_in_, stk_out_;
public:
    CQueue() {

    }
    
    void appendTail(int value) {
        stk_in_.push(value);
    }
    
    int deleteHead() {
        if(!stk_out_.empty()) {
            int ans = stk_out_.top();
            stk_out_.pop();
            return ans;
        } else if(!stk_in_.empty()) {
            while(stk_in_.size() != 1) {
                int tmp = stk_in_.top();
                stk_in_.pop();
                stk_out_.push(tmp);
            }
            int tmp = stk_in_.top();
            stk_in_.pop();
            return tmp;
        } else {
            return -1;
        }
    }
};

本代码提交AC,用时696MS。

剑指 Offer 07. 重建二叉树

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:

3

/ \
9 20
/ \
15 7
 

限制:

0 <= 节点个数 <= 5000

注意:本题与主站 105 题重复:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


给定二叉树的前序和中序遍历,要求重构出原始二叉树。

前序:根、左、右;中序:左、根、右。所以每次把前序数组的第一个元素作为根节点,然后在中序中找到根节点,把中序划分为两半,由此可知道左、右子树子数组的长度,据此把前序也划分为左、右两部分,递归调用。为了快速找到根节点在中序数组中的位置,提前用hash表存储。完整代码如下:

class Solution {
private:
    TreeNode* buildTree(vector<int>& preorder, int pl, int pr, vector<int>& inorder, int il, int ir, unordered_map<int,int> &hash) {
        if(pr < pl || ir < il) return NULL;
        TreeNode *root = new TreeNode(preorder[pl]);
        int im = hash[preorder[pl]];
        int len_left = im - il, len_right = ir - im;
        root->left = buildTree(preorder, pl + 1, pl + len_left, inorder, il, im - 1, hash);
        root->right = buildTree(preorder, pl + len_left + 1, pr, inorder, im + 1, ir, hash);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int,int> hash;
        for(int i = 0; i < inorder.size(); ++i) hash[inorder[i]] = i;

        int n = preorder.size();
        return buildTree(preorder, 0, n - 1, inorder, 0, n - 1, hash);
    }
};

本代码提交AC,用时32MS。

LeetCode Maximum Sum Circular Subarray

918. Maximum Sum Circular Subarray

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array.  (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once.  (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

Example 1:

Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3

Example 2:

Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Example 3:

Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Example 4:

Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3

Example 5:

Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1

Note:

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

给定一个循环数组,即数组的最后一个和数字第一个连起来了。求循环数组的最大连续子数组和。

LeetCode Maximum Subarray的升级版,即数组首尾相连了。我一开始想到的解法是,既然数组首尾相连了,那就2*n次dp即可,即把原数组复制一遍,接到原数组后面,形成2*n长的数组,然后照样跑原来的DP算法。这个解法是不对的,比如如果数组是[1,2,3,4]这种全是正数,则跑2n遍之后,ans会一直max更新,导致最后的ans是1+…+4+1+…4,即数组加了两遍,每个数重复加了。另外对于数组[5,-3,5]这种,也会完整数组加两遍。

正确解法是,分两种情况,第一种情况是最大子串和没有跨越首尾,则使用常规DP即可求解。第二种情况是,最大子串和跨越了首尾,则可以把问题转化为求原数组的最小连续子串和,然后用数组总和减去最小连续子串和,就能得到跨越首尾的最大连续子串和。在求解第二种情况时,需要注意如果最小连续子串和是整个数组的情况,比如数组都是负数[-1,-2,-3],则求到的最小连续子串和是整个数组[-1,-2,-3],用数组总和一减变成了空集和为0,但最大连续子串和至少需要1个元素,对于这种情况,丢弃case2的解。

完整代码如下:

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int n = A.size();
        vector<int> dp(n, 0);
        
        // 最大连续子串
        dp[0] = A[0];
        int ans1 = A[0], sum = A[0];
        for(int i = 1; i < n; ++i) {
            dp[i] = max(dp[i - 1], 0) + A[i];
            ans1 = max(ans1, dp[i]);
            
            sum += A[i];
        }
        
        // 最小连续子串
        fill(dp.begin(), dp.end(), 0);
        dp[0] = A[0];
        int ans2 = A[0];
        for(int i = 1; i < n; ++i) {
            dp[i] = min(dp[i - 1], 0) + A[i];
            ans2 = min(ans2, dp[i]);
        }
        
        if(ans2 == sum) ans2 = INT_MIN; // 注意最小连续子串和不能是全长数组
        else ans2 = sum - ans2;
        
        return max(ans1, ans2);
    }
};

本代码提交AC,用时252MS。

剑指 Offer 36. 二叉搜索树与双向链表

剑指 Offer 36. 二叉搜索树与双向链表

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。

为了让您更好地理解问题,以下面的二叉搜索树为例:

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

注意:本题与主站 426 题相同:https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

注意:此题对比原题有改动。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


如何将二叉搜索树转换in-place转换为有序双向链表。

此题同时考察了多个知识点,首先二叉搜索树转换为有序结果,需要使用二叉树的中序遍历,然后要in-place转换为双向链表,则需要在遍历二叉树的过程中,对每个节点,修改其left和right指针,使其分别指向转换后的双向链表的前驱和后继节点。

使用递归的方法,设置两个全局变量pre和head,分别表示当前遍历节点的前驱节点,以及转换后的双向链表的头结点。完整代码如下:

class Solution {
private:
    Node *pre, *head;
    void DFS(Node *root) {
        if(root == NULL) return;

        DFS(root->left);
        if(head == NULL) head = root;
        else pre->right = root;
        
        root->left = pre;
        pre = root;
        DFS(root->right);
    }
public:
    Node* treeToDoublyList(Node* root) {

        if(root == NULL) return NULL;

        pre = head = NULL;

        DFS(root);

        head->left = pre;
        pre->right = head;

        return head;
    }
};

本代码提交AC,用时12MS。

LeetCode Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Given an array nums and an integer target.

Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).

Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

Example 3:

Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10
Output: 3

Example 4:

Input: nums = [0,0,0], target = 0
Output: 3

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 0 <= target <= 10^6

给定一个数组,问数组中最多有多少个不overlap的子数组,它们的和等于target。

常规DP方法,假设dp[i]表示[0,…,i]能找到的最多的子串数目,则对于nums[i+1],如果从i+1往前,求累加和,如果累加到j的地方,累加和[j,…,i]等于target,则dp[i+1]=dp[j-1]+1。

这种思路的代码如下,需要注意for循环需要满足dp[j]==dp[i],如果dp[j]<dp[i],说明j已经回退到上一个累加和等于target的区间,已经有overlap了,需要终止。

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> dp(n + 1, 0);
        for(int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1];
            int sum = 0;
            for(int j = i; j > 0 && dp[j] == dp[i]; --j) {
                sum += nums[j - 1];
                if(sum == target) dp[i] = max(dp[i], dp[j - 1] + 1);
            }
        }
        return dp[n];
    }
};

上述代码的时间复杂度为O(n^2),在最后几个大数据集上TLE。

参考评论区,用一个hash记录某个前缀和出现的最新下标,对于任意一个数nums[i],看看prefix_sum-target是否在之前记录的前缀和中(查hash即可),如果在,假设对应下标为j,则说明[j,…,i]之间的累加和等于target,找到一个。不过为了保证不overlap,需要保证下标j不能回退到上一个合法的累加和区间内,每次找到一个合法区间后,用right_most记录其右边界,下次只需要用j和right_most比较大小即可。

完整代码如下:

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int n = nums.size();
        unordered_map<int, int> hash;
        hash[0] = -1;
        int prefix_sum = 0, right_most = -1;
        int ans = 0;
        for(int i = 0; i < n; ++i) {
            prefix_sum += nums[i];
            int supplement = prefix_sum - target;
            if(hash.find(supplement) != hash.end()) {
                int left = hash[supplement];
                if(left >= right_most) {
                    ++ans;
                    right_most = i;
                }
            }
            hash[prefix_sum] = i;
        }
        return ans;
    }
};

本代码提交AC,用时392MS。