题目
有一个机器人可以通过接收一系列命令来移动。
命令序列中有四种类型的命令：
机器人向上移动一个单位。
D:机器人向下移动一个单位。
L:机器人向左移动一个单位。
R：机器人向右移动一个单位。
现在，给定一个长度为n的命令序列。您需要找出命令序列中有多少子字符串满足以下条件：如果机器人执行子字符串命令，它可以返回到起始位置。
子字符串是字符串中连续的字符序列。例如，“best of”是“It was the best of times”的子字符串。例如，“Itwastimes”是“It was best of times”的子序列，但不是子字符串。
输入
此问题包含多个测试用例。
第一行包含一个整数t（1≤T≤20） 指示测试用例的数量。
对于每个测试用例，第一行包含一个整数n（2≤N≤105).
第二行包含长度为n的UDLR字符串。
输出
对于每个测试用例，输出一行一个整数表示答案。
输出案例
1? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2
6
URLLDR
思路1
暴力枚举，算法复杂度O(n*2)
枚举每一个区间，记录x，y的值，区间的x和y最后等于0，满足条件，和加一。但是题目给的n<=1e5,使用暴力枚举肯定会超时。所以有没有更好的方法呢？答案肯定是有。
思路2
前缀和O(n)
前缀和是一种重要的预处理，能大大降低查询的时间复杂度。可以简单理解为“数列的前n项的和”。
前缀和可以求区间的和，比如[l,r]区间的和为sum[r]-sum[l-1];题目问的是如何某区间后还能回到原位，意思是寻找sum[l-1]==sum[r]的区间个数,这个区间的和为0。这个题目有两个元素，x和y，所以我们要进行维护x,y的值。所以我们需要用到pair<int,int>,并用map计数。用法为map<pair<x,y>,int>进行计数。那么计数完之后我们知道了每个pair<x,y>有多少个，那么我们怎么计算有多少个sum[l-1]==sum[r]这样的区间呢？一种算法是。还有一种是累加，从0累加到n-1；
C++代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<pair<int, int>, ll> cnt;
char a[100010];
int main()
{
int t;
scanf("%d", &t);
while (t --) {
ll res = 0;
cnt.clear();
ll n;
ll x = 0, y = 0;
cnt[{0,0}] = 1;
scanf("%d", &n);
scanf("%s", a + 1);
for (int i = 1;i <= n;i ++) {
int id;
if(a[i] == 'U') x++;
else if(a[i] == 'L') y++;
else if(a[i] == 'D') x--;
else if(a[i] == 'R') y--;
res += cnt[{x,y}];
cnt[{x,y}] ++;
}
cout << res << endl;
}
return 0;
}