【解法1】暴力解：枚举
原始讲义 · 非增强校订版 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 【解法1】暴力解：枚举
(1)使用双指针i,j分别指向a,b，同步遍历。每次移动指向较小元素的指针，才有可能获得更小的距离。
(2) 伪代码如下：
int ans(int a[], int b[], int n)
{
int D_min = INT_MAX;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
D_min = min(D_min, abs(a[i] - b[j]));
return D_min;
}
(3)时间复杂度：O(n²) // 空间复杂度：O(1)
int ans(int a[], int b[], int n)
{
int D_min = INT_MAX;
int i = 0, j = 0;
while (i<n && j<n)
{
D_min = min(D_min, abs(a[i]- b[j]));
if (a[i]<b[j]) i++;
else j++;
}
return D_min;
}
int ans(int A[], int n, int k)
{
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
if (i!=j && A[i]+A[j]==k) return 1;
return 0;
}
(3) // 时间复杂度：O(n²) 空间复杂度：O(1)
int B_Search(int A[], int L, int R, int x)
{
while (L <= R)
{
int mid = (L + R) / 2;
if (A[mid] == x) return mid;
if (x < A[mid]) R = mid - 1;
else L = mid + 1;
}
return -1;
}
int ans(int A[], int n, int k)
{
for (int i = 0; i < n; i++)
{
int j = B_Search(A, 0, n - 1, k - A[i]);
if (j != -1 && i != j) return 1;
}
return 0;
}
(3)时间复杂度：O(nlogn) // 空间复杂度：O(1)
int ans(int A[], int n, int k)
{
int count[k+1] = {0}; //散列表记录某个数出现的次数
for (int i = 0; i < n; i++)
{
if (A[i] > k) continue;
if (count[k-A[i]] > 0) return 1; //找到A[i]和k-A[i]
count[A[i]]++;
}
return 0;
}
(3) // 时间复杂度： O(n) 空间复杂度：O(k)
int ans(int A[], int n, int k)
{
int j = n-1;
for (int i = 0; i < n; i++)
{
while (i<j && A[i]+A[j]>k) j--;
if (i >= j) return 0;
if (A[i] + A[j] == k) return 1;
}
}
(3) // 时间复杂度： O(n) 空间复杂度：O(1)
int ans(int A[], int B[], int n)
{
int C[n];
int k = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (A[i] == B[j]) C[k++] = A[i];
输出数组 C
}
(3) // 时间复杂度：O(n²) 空间复杂度：O(n)
int ans(int A[], int B[], int n)
{
int C[n];
int i = 0, j = 0, k = 0; // i、j作为遍历A、B的下标
while (i<n && j<n) //直到有一个数组遍历完
{
if (A[i] == B[j]) //数组A和B中都存在的元素存入C中
{
C[k++] = A[i++];
j++;
}
if (A[i] < B[j]) i++; // A[i]更小，i指针后移
if (A[i] > B[j]) j++; //B[j]更小，j指针后移
}
输出数组C
}
//快速排序
void Qsort(int A[], int L, int R)
{
if (L >= R) return; //区间内元素个数为0或 1，自然有序，递归
终止
int i = L, j = R;
int pivot = A[L]; // 选取区间第一个元素作为基准
// 不断交换左边比 pivot 大的数和右边比 pivot 小的数
while (i < j)
{
while (i < j && A[j] >= pivot) j--; // 从右向左找第一个小于 pivot 的数
while (i < j && A[i] <= pivot) i++; // 从左向右找第一个大于 pivot 的数
if (i < j) swap(A[i], A[j]);
//将基准值 A[L]与 A[i] 交换
swap(A[L], A[i]);
//递归处理左右两个子区间
Qsort(A, L, i - 1);
Qsort(A, i + 1, R);
}
int ans(int A[], int n)
{
Qsort(A, 0, n-1);
return A[0];
}
}
(3) // 时间复杂度：O(nlogn) 空间复杂度：O(logn)
int ans(int A[], int n)
{
int A_min = A[0];
for (int i = 1; i < n; i++)
A_min = min(A[i], A_min);
return A_min;
}
(3) // 时间复杂度：O(n) 空间复杂度：O(1)
int B_Search(int A[], int L, int R)
{
while (L < R)
{
int mid = (L + R) / 2;
if (A[mid] <= A[R]) R = mid;
else L = mid + 1;
}
return L;
}
int ans(int A[], int n)
{
return A[B_Search(A, 0, n - 1)];
}
int ans(int A[], int n, int k)
{
int count = 0;
int s[n + 1] = {0};
for (int i = 0; i < n; i++) s[i + 1] = s[i] + A[i];
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
if (s[j + 1] - s[i] <= k) count++;
return count;
}