【解法1】暴力解：枚举
强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 【解法1】暴力解：枚举
(1) 二重循环i和j扫描数组，当i和j不相等且A[i]+A[j]== k时返回1，如果扫描完都没找到则返回0。(2）伪代码如下：
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;
}
//折半查找
int B_Search(int A[], int L, int R, int x)
{
int mid;
while (L <= R)
{
mid = (R + L) / 2;
if (A[mid] == x)
return mid;
else
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 (i != j) return 1; // 需要保证 i 和 j 不相等
}
return 0;
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) break;
if (count[k-A[i]] > 0) return 1; // 找到A[i]和k-A[i]
count[A[i]]++;
} return 0;
}
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;
}
}
int ans(int A[], int B[], int n)
{
int C[n], i = 0, j = 0, k = 0;
while (i < n && j < n)
{
if (A[i] == B[j]) { C[k++] = A[i]; i++; j++; }
else if (A[i] < B[j]) i++;
else j++;
}
output(C, k);
return k;
}
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; //区间≤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];
}
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;
}
int B Search(int A[], int L, int R)
{ int mid;
while (L < R)
{ 如果L>R则退出循环
mid = (L+R)/2; // mid取中间数，向下取整
if (A[mid] <= A[R]) R = mid; //取左一半
else L = mid + 1; //取右一半
}
return L;
int ans(int A[], int n)
{
int i = B_Search(A, 0, n-1);
return A[i];
}
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;
}
int ans(int A[], int n, int k)
{
int count = 0;
int sum = 0;
int i = 0; //窗口左边界
for (int j = 0; j < n; j++) // j 是窗□右边界
{
sum += A[j];
{ while (sum > k)
sum -= A[i];
i++;
}
count += (j - i + 1);
}
return count;
}
int ans(int A[], int B[], int n)
{
int t = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (A[i] + B[j] <= 5 * n) t++;
return t;
}