두 배열과 목표값이 주어졌을 때, 두 배열의 부 배열의 합이 목표하는 값이 되는 경우의 수를 구하는 문제입니다. 먼저 부 배열의 합이 될 수 있는 경우는 A는 $\frac{n(n+1)}{2}$개, B는 $\frac{m(m+1)}{2}$개가 있습니다. 문제의 조건에서 n과 m은 1000 이하라는 조건이 주어졌으므로 적어도 $O((n^2+m^2)\log(nm))$의 시간 복잡도 이내에는 답을 구하야겠습니다. 모든 경우를 일일이 탐색하면 $O(n^2m^2)$이므로 좋지 않은 방법인 것 같습니다.
이 문제를 두 절차로 나누어 생각해보면 조금 답이 나올 것 같기도 합니다. 먼저 두 배열에 대해 부 배열의 합을 새로운 배열로 옮기는 문제와 두 배열의 원소를 하나씩 골랐을 때 합이 T인 원소 조합을 구하는 문제입니다. 먼저 첫 번째 문제는 부 배열의 가짓수가 $\frac{n(n+1)}{2}$개이므로 시간 복잡도 $O(n^2+m^2)$(A와 B 각각에 대한 시간 복잡도입니다!)에 얻을 수 있습니다. 이제 두 번째 문제를 해결해야하는데, 이것은 두 배열을 모두 정렬 후 이분 탐색 또는 투 포인터를 이용하여 구할 수 있습니다. 배열의 크기가 $O(n^2)$이므로 정렬은 $O(n^2\log{n}+m^2\log{m})$의 시간 복잡도에 해결할 수 있습니다. 이분 탐색과 투 포인터 모두 정렬보다는 시간 복잡도가 약간 작기 때문에 기호에 맞는 방법으로 풀면 됩니다.(저는 투 포인터 썼습니다)
PS알못 OrbitHv의 PS